Description
Find unique combinations of distinct positive candidates summing to target. A candidate may be reused; combination order is irrelevant.
Solution
def combination_sum(candidates, target):
result = []
def visit(start, remaining, path):
if remaining == 0:
result.append(path[:])
return
for i in range(start, len(candidates)):
if candidates[i] <= remaining:
path.append(candidates[i])
visit(i, remaining-candidates[i], path)
path.pop()
visit(0, target, [])
return resultExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[2,5],7]- Output
[[2,5]]
2 plus 5 reaches 7.
Example 2
- Input
[[3],6]- Output
[[3,3]]
The candidate 3 may be reused.
Example 3
- Input
[[4],3]- Output
[]
The only candidate exceeds the target.
Approach
Backtrack with a start index so combinations are built in one order. Reuse the current index when choosing again.
Time & space
O((c + 1)^d * d) conservative time bound; O(d) stack excluding output, where c is candidate count and d = target / smallest candidate.