39. Combination Sum

递归法

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        candidates = sorted(candidates)
        self.combinationSumDFS(candidates, target, 0, res, [])
        return res
    
    def combinationSumDFS(self, candidates, target, start, res, path):
        if target < 0:
            return
        if target == 0:
            print('path', path)
            res.append(path)
            return;
        for i in range(start, len(candidates)):
            if candidates[i] > target:
                return
            self.combinationSumDFS(candidates, target-candidates[i], i, res,path+[candidates[i]])

        

回溯思想
与上述代码类似，但是需要注意path的深拷贝和浅拷贝问题

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        candidates = sorted(candidates)
        self.combinationSumDFS(candidates, target, 0, res, [])
        return res
    
    def combinationSumDFS(self, candidates, target, start, res, path):
        if target < 0:
            return
        if target == 0:
            print('path,i', path,start)
            res.append(list(path))
            return;
        for i in range(start, len(candidates)):
            if candidates[i] > target:
                return
            path.append(candidates[i])
            self.combinationSumDFS(candidates, target-candidates[i], i, res,path)
            path.pop()