边工作边刷题：70天一遍leetcode: day 34-2

Combination Sum

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        def dfs(candidates, start, target, res, solutions):
            n = len(candidates)
            if target==0:
                resCp=list(res)
                solutions.append(resCp)
                return
            
            if start>=n or target<0:
                return
            
            for i in range(start, n):
                if i!=start and candidates[i]==candidates[i-1]: continue
                res.append(candidates[i])
                dfs(candidates, i, target-candidates[i], res, solutions)
                res.pop()
        
        candidates = sorted(candidates)
        res = []
        solutions = []
        dfs(candidates, 0, target, res, solutions)
        return solutions