Python 88ms dfs solution


  • 0
    T
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort()
        return self.combine(candidates, target, 0)
            
    def combine(self, candidates, target, s):
        res = []
        for i in xrange(s, len(candidates)):
            if target <= candidates[i]:
                if target == candidates[i]:
                    res.append([candidates[i]])
                break
            
            target2 = target - candidates[i]
            if target2 >= candidates[i]:
                for row in self.combine(candidates, target2, i):
                    res.append([candidates[i]]+row)
                
        return res
    

    Doing list add ([1,2]+[2,3]) only when it succeeds. Sorting before everything to ensure no duplication and non-descending order.


Log in to reply
 

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