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)
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.
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.
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?
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)
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)
Thank you, I love your solution! Because all the candidates are positive, we don't really need to sort tho.
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, )
@caikehe no need to use sort() ?
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?
Sorting of the original array makes all resultant arrays increasing. (i.e. [2,2,3] and  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)
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?
Please notice that there is a variable called index in function dfs. Hope that helps.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.