Here is the implementation:
function combinationSum(candidates, target):
result = []
backtrack(0, [], 0)
return result
function backtrack(start, current, currentSum):
if currentSum == target:
result.append(copy of current)
return
if currentSum > target:
return
for i from start to candidates.length - 1:
current.append(candidates[i])
backtrack(i, current, currentSum + candidates[i])
current.pop()
Note: backtrack(i, ...) not backtrack(i+1, ...) allows reuse. Time depends on the number of valid combinations.