135. 数字组合

中文 English

给定一个候选数字的集合 candidates 和一个目标值 target. 找到 candidates 中所有的和为 target 的组合.

在同一个组合中, candidates 中的某个数字不限次数地出现.

样例

样例 1:

输入: candidates = [2, 3, 6, 7], target = 7
输出: [[7], [2, 2, 3]]

样例 2:

输入: candidates = [1], target = 3
输出: [[1, 1, 1]]

注意事项

1. 所有数值 (包括 target ) 都是正整数.
2. 返回的每一个组合内的数字必须是非降序的.
3. 返回的所有组合之间可以是任意顺序.
4. 解集不能包含重复的组合.

class Solution:
    """
    @param candidates: A list of integers
    @param target: An integer
    @return: A list of lists of integers
    """
    def combinationSum(self, candidates, target):
        # write your code here
        result = []
        self.dfs(sorted(list(set(candidates))), target, result, path=[], start_index=0)
        return result
    
    def dfs(self, nums, target, result, path, start_index):
        if target == 0 and path:
            result.append(list(path))
        
        if target < 0:
            return
        
        for i in range(start_index, len(nums)):
            path.append(nums[i])
            self.dfs(nums, target-nums[i], result, path, i)
            path.pop()