Recursion & Backtracking/Practice/Combination Sum
Combination Sum - Backtracking Explained Visually
Build combinations as a decision tree: at each candidate you either reuse it (stay) or move past it forever (advance). When the running total hits the target, record the path; when it overshoots, prune that branch. Undo each choice on the way back up.
Why it works
The tree has every combination exactly once because "stay" and "move past" encode reuse without duplicates. Sorting the candidates first lets you stop exploring a branch the moment the sum overshoots - pruning dead subtrees instead of walking them.
The problem
Given an array of distinct integers candidates and a target integer target, return all unique combinations of candidates where the chosen numbers sum to target. The same number may be used multiple times.
Hints
- Use backtracking with a remaining sum.
- Pass the current index (not index+1) to allow reuse of the same element.
- Sort candidates first to enable early termination when candidates[i] > remaining.
Test cases
| Input | Expected |
|---|---|
combination_sum([2,3,6,7], 7) | [[2,2,3],[7]] |
combination_sum([2,3,5], 8) | [[2,2,2,2],[2,3,3],[3,5]] |
Reference starter code
def combination_sum(candidates, target):
result = []
def backtrack(start, path, remaining):
if remaining == 0:
result.append(path[:])
return
for i in range(start, len(candidates)):
if candidates[i] > remaining:
continue
path.append(candidates[i])
# pass i (not i+1) to allow reuse
backtrack(i, path, remaining - candidates[i])
path.pop()
backtrack(0, [], target)
return result
print(combination_sum([2, 3, 6, 7], 7)) # [[2,2,3],[7]]
print(combination_sum([2, 3, 5], 8)) # [[2,2,2,2],[2,3,3],[3,5]]
Try it yourself
Solve it in the browser editor with real test cases and instant feedback - free, no signup needed.