Core Insight Build one partial answer at a time and undo each choice so sibling branches start clean.
Common Pitfall Copy a completed path before appending it to results; later mutations must not alter it.
Description
Find all combinations that sum to target, each number used once.
Constraints
- Time Complexity:
O(2^n) - Space Complexity:
O(n)
Tags
arraybacktracking
Implementation Plan Translate the invariant into these small, testable moves.
- Choose a candidate.
- Record the choice.
- Explore the next decision.
- Undo the choice before trying the next candidate.
def combinationSum2(candidates, target):
candidates.sort()
res = []
def backtrack(cur, pos, target):
if target == 0:
res.append(cur.copy())
return
if target <= 0:
return
prev = -1
for i in range(pos, len(candidates)):
if candidates[i] == prev:
continue
cur.append(candidates[i])
backtrack(cur, i + 1, target - candidates[i])
cur.pop()
prev = candidates[i]
backtrack([], 0, target)
return res