Backtracking · LC #39
Combination Sum
Backtrack over sorted candidates; recurse with the same index (allowing reuse) and prune branches where the candidate exceeds the remaining target.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given distinct integers `candidates` and a `target`, return all unique combinations where chosen numbers sum to `target`. Each number may be used unlimited times.
Sample I/O
Input: candidates=[2,3,6,7], target=7 Output: [[2,2,3],[7]] Input: candidates=[2,3], target=6 Output: [[2,2,2],[3,3]]
Intuition
How to Think About It
Intuition
Same backtracking template as Subsets, with two key differences: (1) record only at remaining==0 (leaf nodes), and (2) pass i (not i+1) to allow reusing the current candidate.
Core Concept
Sort candidates. bt(start, curr, remaining): if remaining==0, record curr. For i from start: if candidates[i]>remaining break (pruning). Push, recurse with bt(i, ...) allowing reuse, pop.
When to use
Find all ways to sum to a target using elements with repetition; coin change enumeration; partition problems with repetition.
When NOT to use
When each element can be used only once (Combination Sum II - LC 40); when you only need count of ways (use DP); when target is large and candidates are few (DP is faster).
Key Insights
What to Know Cold
- Key difference from Subsets: pass i (not i+1) to bt - enables element reuse.
- Sorting + break-when-exceeded is critical pruning that avoids exploring dead branches.
- Record only at remaining==0 (leaf) unlike Subsets which records at every node.
- No visited array needed - the start index + sorted order prevents duplicate combinations.
- Stack depth bounded by target / min_candidate.
1 example
Worked Examples
Ways to make change for 7 cents
candidates=[2,3,6,7], find all combos summing to 7.
Sorted backtracking with reuse (pass i not i+1) and pruning.
Output: [[2,2,3],[7]]
Coin change enumeration, knapsack enumeration, and budget allocation all share this reuse-allowed combination pattern.