Combination Sum
Picture
With candidates 2,3 and target 7, the sequence 2,2,3 works. Choosing 2 does not remove it from future choices.
Predict
Why recurse with the same index after choosing a value?
Walk through the small example
That value may be reused. A nondecreasing choice index removes permutation duplicates while preserving repeated values.
Mental model and complete Python solution
Order the coin types, not the output sequence. The current index says which values may still appear, so every multiset combination has one canonical nondecreasing path.
What the function promises: Return lexicographically ordered combinations. Candidates are distinct positive integers and target is nonnegative.
def combination_sum(candidates, target):
if target < 0 or any(value <= 0 for value in candidates) or len(set(candidates)) != len(candidates):
raise ValueError("Invalid input")
candidates = sorted(candidates)
answer, path = [], []
def build(start, remaining):
if remaining == 0:
answer.append(path[:]); return
for i in range(start, len(candidates)):
value = candidates[i]
if value > remaining: break
path.append(value); build(i, remaining-value); path.pop()
build(0, target)
return answer
assert combination_sum([2,3,6,7], 7) == [[2,2,3],[7]]
assert combination_sum([2], 1) == []Work and storage: Output-sensitive exponential time; active recursion/path depth is at most target/min(candidate).
When to recognize it: A nondecreasing choice index removes permutation duplicates while preserving repeated values.
Check before applying it: Zero or negative candidates break decreasing-remainder termination.
Change one rule
Each candidate may be used once and duplicates appear in input.
See what changes
Advance to i+1 after choosing and use the depth-local duplicate skip from unique permutations.
Connect
backtracking: The path owns chosen values and undoes after exploration.
pruning: Sorted positive candidates justify stopping after one overshoot.