Combination sum
Why it exists
Problem: We want all combinations of numbers that sum to a target, where we can reuse numbers infinitely. Naive subset generation doesn't allow reuse, and unconstrained reuse leads to infinite recursion.
Better idea: Pass a `start_index` to enforce ordering (so we generate `[2, 3]` but never `[3, 2]`), and allow reuse by recursing with the SAME index `i` instead of `i + 1`. Sort the input to prune the search immediately when candidates exceed the target.
Mental model
Drawing coins from a sorted pile to make exact change. You can keep taking the same coin as long as you don't overshoot the target.
Target-driven search. The state is `(start_index, remaining_target, current_path)`. We iterate through candidates from `start_index`. If we pick a candidate, we stay on the same index for the next call to allow reuse. We stop picking when the target drops below zero.
Repeated decision: Should I add the candidate at index `i` to my path and subtract its value from the target?
Explanation
Combination Sum introduces a twist: unbounded element reuse.
In standard subsets, when you pick an element at index `i`, you recurse with `i + 1` so you don't pick it again. Here, you recurse with the SAME index `i`.
But wait, if we can reuse elements, why don't we get duplicates like `[2, 3]` and `[3, 2]`?
The answer is the `start_index`. The loop always starts at `start_index`, never earlier. This enforces a strictly non-decreasing sequence in our path. The path can never contain a smaller index *after* a larger one. Thus, each multiset is produced exactly once, in one canonical order.
**Pruning:**
If we sort the input array ascending, we unlock massive pruning. Inside the loop, if `candidates[i] > remaining_target`, we don't just skip it—we `break` the entire loop. Because the array is sorted, every subsequent candidate will also be too large. This cuts off massive dead branches instantly.
**Hand-trace:** `candidates=[2,3,6,7]`, `target=7`
- Choose 2, remaining 5. Recurse (index 0).
- Choose 2, remaining 3. Recurse (index 0).
- Choose 2, remaining 1. Recurse (index 0).
- Choose 2, remaining -1. Dead end.
- Choose 3. remaining 0. Record `[2,2,3]`.
- Skip 2, choose 3... etc.
- Skip up to 7, choose 7. Record `[7]`.
Key points
- The Aha Moment: Reuse means recursing with the SAME index. Deduplication is handled automatically by never looking backward.
Pattern: Target-Driven Unbounded Backtracking
Recognition cues:
- Elements can be reused an unlimited number of times
- Find all combinations summing to target
Engineering examples
Change-making systems
Finding all ways to provide exact change using a specific set of coin denominations.
Combinatorial enumeration of coin reuses.
Common mistakes
- Recursing with i + 1: If you recurse with `i + 1`, you prevent reuse, turning this into a standard subset-sum problem.
- Pruning without sorting: If you break the loop when `candidates[i] > remaining_target`, but the array isn't sorted, you will incorrectly prune valid smaller candidates that appear later.
Recall questions
- How does Combination Sum allow for element reuse in the backtracking tree?
- Why doesn't allowing element reuse generate duplicate combinations like [2,3] and [3,2]?
- How does sorting the input array optimize Combination Sum?
Questions & answers
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations where the chosen numbers sum to target.
Sort candidates. Backtrack with `(start, remaining, path)`. Loop `i` from `start` to `n-1`. Break if `candidates[i] > remaining`. Else, path append, backtrack with `(i, remaining - candidates[i], path)`, path pop.
Approach: Combination sum with pruning.
How can you modify the Combination Sum algorithm to only allow each element to be used once (Combination Sum II)?
Change the recursive call to pass `i + 1` instead of `i`. To handle duplicates in the input, skip elements where `i > start` and `candidates[i] == candidates[i - 1]`.
Approach: Combination sum without reuse, adding a duplicate-skipping invariant.
Continue learning
Previous: Backtracking template