Subsets and Combination Sum
The previous page built every subset and rejected nothing. Now the same tree gets a constraint bolted on: only keep the subsets that add up to a target. That one requirement is enough to show what pruning actually does to a search.
Two ways to write the subset tree
There are two standard formulations, and they produce differently shaped trees for the same answers.
| Formulation | Branching | Tree shape |
|---|---|---|
| Include or exclude item i, then move to i+1 | Always 2 | A perfect binary tree of depth n, 2^n leaves |
| Loop over remaining items, recurse from i+1 | Shrinks as you go | Depth n, 2^n nodes total, every node an answer |
Everything on this page uses the second one. It generalises to permutations, n-queens and colouring without changing shape, whereas the include/exclude version is specific to picking a subset of a fixed list.
Adding the constraint
Combination sum asks for every subset of a candidate list that totals exactly some target. The naive way is to build all 2^n subsets and test each one. That works, and it is wasteful in a way that is easy to see once you watch it.
If the running total is already past the target and every candidate is positive, nothing below that node can ever come back down to it. The entire subtree is dead, and it is dead the moment you compute the total, not several levels later when a leaf gets tested.
Compare the two runs
Switch pruning off and on below. Same candidates, same target, same answers. Watch the node counter.
Candidates 2, 3, 5, 6, 8, each usable once. Target 10.
Looking for combinations summing to 10, rejecting any branch that overshoots.
With pruning off the search enters 29 nodes. With it on, 13, and 8 branches get cut before they are built. Both find the same two answers. The unpruned version spends most of its time in subtrees that were doomed at the second level.
That ratio grows quickly. Five candidates is small enough that both runs finish instantly; at twenty candidates the pruned version is still fine and the naive one is building a million subsets to test.
Why the list is sorted
The candidates are sorted ascending, and that is load-bearing. It lets the rejection use break rather than continue.
If candidate i already pushes the total past the target, then candidate i+1 is at least as large and pushes it further. There is no point testing the rest of the loop. On an unsorted list that reasoning collapses and you are back to skipping one candidate at a time.
function combinationSum(candidates, target) {
const sorted = [...candidates].sort((a, b) => a - b); // required for the break
const out = [];
const current = [];
function backtrack(start, sum) {
if (sum === target) {
out.push([...current]);
return; // all candidates positive, so going deeper cannot help
}
for (let i = start; i < sorted.length; i++) {
// Sorted, so if this one overshoots, so does everything after it.
if (sum + sorted[i] > target) break;
current.push(sorted[i]); // choose
backtrack(i + 1, sum + sorted[i]); // explore
current.pop(); // un-choose
}
}
backtrack(0, 0);
return out;
}
// combinationSum([2, 3, 5, 6, 8], 10) -> [[2, 3, 5], [2, 8]]The variants you will actually be asked for
Combination sum shows up in three flavours, and they differ by one line each.
| Variant | The change |
|---|---|
| Each candidate used at most once | Recurse with i + 1, as above |
| Candidates may be reused without limit | Recurse with i instead of i + 1 |
| Input has duplicates, answers must not repeat | Sort, then skip when i > start and candidates[i] === candidates[i-1] |
That third rule is worth staring at. The condition is i > start, not i > 0. The first occurrence of a repeated value at a given level is allowed; later ones would start a subtree identical to one already built. The same idea comes back on the next page for permutations, in a slightly different disguise.