Python solution beats 98%


  • 0

    class Solution(object):

    def dfs(self, candidates, path, target, ret):
        n = len(candidates)
        if n == 0 or target < candidates[0]:
            return
        i = n - 1
        while i >= 0:
            while 0 <= i < n - 1 and candidates[i] == candidates[i + 1]:
                i -= 1
            if i == -1:
                return
            if candidates[i] == target:
                ret.append([candidates[i]] + path)
            elif candidates[i] < target:
                self.dfs(candidates[:i], [candidates[i]] + path, target - candidates[i], ret)
            i -= 1
        return
    
    
    
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates, ret = sorted(candidates), []
        self.dfs(candidates, [], target, ret)
        return ret

Log in to reply
 

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