Python DFS solution, beat 92.80%


  • 0
    T
    class Solution(object):
        def combinationSum(self, candidates, target):
            """
            :type candidates: List[int]
            :type target: int
            :rtype: List[List[int]]
            """
            candidates.sort()
            self.res = []
            def dfs(candidates, target, path):
                if target == 0: 
                    self.res.append(path)
                if len(candidates) == 0 or candidates[0] > target: return 
                
                # solutions with the first element
                dfs(candidates, target - candidates[0], path + [candidates[0])
                # solutions without the first element
                dfs(candidates[1:], target, path)
    
            dfs(candidates, target, [])
            return self.res 
    

Log in to reply
 

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