Python very easy to understand solution 88 ms


  • 0
    I
    class Solution(object):
        def combinationSum(self, candidates, target):
            """
            :type candidates: List[int]
            :type target: int
            :rtype: List[List[int]]
            """
            res=[]
            self.dfs(res,[],sorted(candidates),target)
            return res
            
        def dfs(self,res,path,candidates,target):
            if target<candidates[0]:
                return 
        # from large values to small values
            for i in range(len(candidates))[::-1]:
                # if equal, it is one solution
                if candidates[i]==target:
                    res.insert(0,[candidates[i]]+path)
                # if smaller, try it and keep searching for candidates that are smaller
                # candidates[:i+1] to avoid duplicates
                elif candidates[i]<target:
                    self.dfs(res,[candidates[i]]+path,candidates[:i+1],target-candidates[i])
                # if larger, do nothing

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.