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, targetnums[i], i, path+[nums[i]], res)
Python dfs solution.


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/dfstoimplementagraphpython
Can you help me to take a look of it?

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:], targetc, path + [c]) return res return helper(candidates, target, [])


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))^(N1): very rough estimate with trial and error only)

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