[leetcode]39. Combin

2023-01-31 05:01:29 leetcode 39. Combin

题目:

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:
[
[7],
[2, 2, 3]
]

意思说 给你一组正数C,然后 给你一个目标数T, 让你从那组C中找到加在一起等于T的那些组合。
比如 给你7 然后 从[2,3,6,7]中可以找到[2,2,3]和[7]两组组合。
想了一下还是用DFS:

就以这个例子举,比如让我找组成7的数
首先那个7肯定是。
然后再看,6,如果6在我们结果里,那还得有能组成7-6=1的数,对吧,然而并没有1,放弃6
再看3,如果要有3,那后面要有能组成7-3=4的数,
发现了什么没有。。
只是从需要组成7的变换成需要组成4的,那写一个函数就可以了。

这个函数的主题逻辑是:
Target =T,然后从数组中找一个数n,然后在 剩下的部分target 变成了 T-n,以此类推。

函数到哪返回呢,如果目标数T=0,则找的成功,返回,如果目标数T小于C中最小的数,言外之意就是我们找到不这样的组合了,寻找失败,返回。
需要注意的是,答案要求没有重复的,如果只是这么写会变成[2,3,2],[2,2,3],[3,2,2],因此要记下 上一个数,我是从小往大找的,也就是说,

如果我已经找完n=2的情况,再去找n=3的时候,3就不应该往回再选n=2了,只能往后走,不然就会重复。

代码如下:



class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        self.resList = []
        candidates = sorted(candidates)
        self.dfs(candidates,[],target,0)
        return self.resList
    def dfs(self, candidates, sublist, target, last):
        if target == 0:
            self.resList.append(sublist[:])
        if target< candidates[0]:
            return 
        for n in candidates:
            if n > target:
                return
            if n < last:
                continue
            sublist.append(n)
            self.dfs(candidates,sublist,target - n, n)
            sublist.pop()

相关文章