Python dfs solution.


  • 53
    C
    def combinationSum(self, candidates, target):
        res = []
        candidates.sort()
        self.dfs(candidates, target, 0, [], res)
        return res
        
    def dfs(self, nums, target, index, path, res):
        if target < 0:
            return  # backtracking
        if target == 0:
            res.append(path)
            return 
        for i in xrange(index, len(nums)):
            self.dfs(nums, target-nums[i], i, path+[nums[i]], res)

  • 1
    W

    Dude, your code is really neat. I saw several examples. I really want to learn how to come up with this kind of idea with each question.


  • 1
    C

    haha, for DFS (backtracking) (BFS as well) you can remember this template, actually more or less they are fixed. So this kind of interview questions is quite easy to handle.


  • 1
    W

    Thanks, it helps me a lot!


  • 0
    Z

    Hi there, I was trying to use your method to implement a graph in python, but I cannot get what I want, my question is posted at Stackoverflow, http://stackoverflow.com/questions/33469897/dfs-to-implement-a-graph-python
    Can you help me to take a look of it?


  • 0
    N
    def dfs(self, cand, target, index, temp, ans):
        if target == 0:
            ans.append(temp)
            return
        if target < cand[index]:
            return
        for i in xrange(index, len(cand)):
            self.dfs(cand, target-cand[i], i, temp+[cand[i]], ans)

  • 0
    N

    maybe faster


  • 9
    H

    hi,caikehe , i think add a break, it will be faster.

    def dfs(self, nums, target, index, path, res):
        if target == 0:
            res.append(path)
            return 
        for i in xrange(index, len(nums)):
            if nums[i] > target:  #here  
                break
            self.dfs(nums, target-nums[i], i, path+[nums[i]], res) 

  • 0

    Thank you, I love your solution! Because all the candidates are positive, we don't really need to sort tho.


  • 0
    C

    It's exciting.Reducing time from 188 ms to 100 ms.


  • 0

    Hi,

    I came up with a similar solution, but using fewer variables, so hopefully it is easier to follow:

            def helper(candidates, target, path, res=[]):
                if not target:
                    res.append(path)
                if target <= 0:
                    return
                for i, c in enumerate(candidates):
                    helper(candidates[i:], target-c, path + [c])
                return res
            return helper(candidates, target, [])
    

  • 0

    @caikehe no need to use sort() ?


  • 0
    C

    Why we need sorting ?


  • 0
    F

    Thank you so much!


  • 0
    S

    What is the complexity of this solution?


  • 0
    N

    This solution uses less code and is faster than append number to path and pop number out from it, but it actually create a new list instance every time it calls self.dfs, I'm a little bit confused here, is the cost of creating list instance cheaper than append/pop?


  • 0
    I

    Can someone explain how this solution avoids duplicates?


  • 0
    M

    @irtazasafi
    @CTD

    Sorting of the original array makes all resultant arrays increasing. (i.e. [2,2,3] and [7] for example but not [3,2,2])
    As along as you don't transverse the same place in the tree twice, there's no duplicates.

    Sorting is efficient because it's only O(N log N), while the O for answer is much larger (somewhat like O((target/min(candidates))^(N-1): very rough estimate with trial and error only)


  • 0
    Z

    Why is it so fast? path+[nums[i]] copies the whole tmp list in every recursive call. I thought using append/pop should be significantly faster than copying the list, but in reality it doesn't

    Does anyone know the reason?


  • 0
    S

    @irtazasafi
    Please notice that there is a variable called index in function dfs. Hope that helps.


Log in to reply
 

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