原題

給出一組候選數(shù)字(C)和目標(biāo)數(shù)字(T),找到C中所有的組合，使找出的數(shù)字和為T。C中的數(shù)字可以無限制重復(fù)被選取。

例如,給出候選數(shù)組[2,3,6,7]和目標(biāo)數(shù)字7
所求的解為：[7] 和 [2,2,3]

注意：

• 所有的數(shù)字(包括目標(biāo)數(shù)字)均為正整數(shù)。
• 元素組合(a1, a2, … , ak)必須是非降序(ie, a1 ≤ a2 ≤ … ≤ ak)。
• 解集不能包含重復(fù)的組合。

解題思路

• backtracking 在代碼的實(shí)現(xiàn)上可以在使用加了再還原的方式，例如：

path.append(candidates[i])
self.helper(candidates, target - candidates[i], path, i, result)
path.pop()

也可以直接把添加的步驟直接通過參數(shù)傳遞的方式，例如：

self.helper(candidates, target - candidates[i], path + [candidates[i]], i, result)

• 與permutation和subset的思考方式類似，DFS
• 每一次向下搜索時，起始位置都和上一次相同，因?yàn)榭梢匀∠嗤夭恢挂淮?，即每次向下傳入?code>index
• For循環(huán)每次從index開始，避免返回到之前的元素

完整代碼

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        result = []
        if not candidates:
            return result
        candidates.sort()
        self.helper(candidates, target, [], 0, result)
        return result
        
    def helper(self, candidates, target, path, index, result):
        if target == 0:
            result.append(path[:])
            return
        
        for i in range(index, len(candidates)):
            if candidates[i] > target:
                break
            self.helper(candidates, target - candidates[i], path + [candidates[i]], i, result)