Subsets and Combination Sum

Subsets and Backtracking

The natural solution is that a state is a partial subset, and a choice is "which item do I add next." Every state is already a valid subset, so every node in the tree records an answer instead of only the leaves.

But now a real problem shows up: if each step can choose any item, you'll build the same subset over and over under different orderings.

To fix this all we need to do is add one more parameter to our recursive function. Pass down a start index and only choose items at or after it, so once you've taken item 2, later steps only consider items 3 onward. Each subset then gets built in exactly one order and shows up exactly once.

Watch the tree

Step through and match the tree against the trace from the introduction. Every node is an answer here, so the count of recorded answers climbs steadily instead of only jumping at the bottom.

Combination sum, where pruning finally shows up

Subsets had no rules to break, so nothing ever got rejected. Combination sum adds one, and it's where the prune from the introduction finally earns its keep.

The task: given candidate numbers and a target, find every combination that sums to exactly the target, where each candidate can be used as many times as you like.

Two things change from subsets. First, since reuse is allowed, a recursive call passes i rather than i + 1, so the same item stays available. Second, and this is the interesting part, you can tell a branch is doomed before you've even finished it. If the running total already blows past the target, no amount of adding more positive numbers is going to bring it back down.

That single check cuts off an entire subtree. Below is the tree for candidates 2, 3 and 5 with target 8, pruning on: step through it and watch every branch get cut the moment a partial sum overshoots.

Watch the branches-cut counter as you go. Each cut is a subtree a generate-and-filter approach would've explored all the way to the bottom before throwing it away. The deeper the tree, the more each cut saves.

Pruning on and off

Switch pruning off and back on. The candidates, the target and the answers all stay the same, so the node counter is the only thing worth watching. That difference is the entire value of thinking about the problem before you write the loop.

One more improvement worth knowing

If the candidates are sorted, the prune gets even stronger. Once you hit a candidate larger than the remaining target, every candidate after it is larger too, so instead of skipping just this one you can stop the loop entirely.

That turns a continue into a break, skipping the rest of the row instead of one cell of it. The sort costs n log n once and pays for itself right away. It's a good habit generally: sorting the input often makes a prune sharper.

The implementation

function combinationSum(candidates, target) {
  const answers = [];
  const current = [];

  function solve(start, remaining) {
    if (remaining === 0) {
      answers.push([...current]);
      return;
    }

    for (let i = start; i < candidates.length; i++) {
      if (candidates[i] > remaining) continue;   // the prune

      current.push(candidates[i]);
      solve(i, remaining - candidates[i]);       // i, not i+1: reuse allowed
      current.pop();
    }
  }

  solve(0, target);
  return answers;
}

Compare this against the subsets code from the introduction. The skeleton hasn't moved. What changed is the stopping test, one prune, and i in place of i + 1.

Where it goes wrong

Passing i + 1 when reuse is allowed, or i when it isn't. These two problems differ by that single character, and getting it wrong produces answers that look plausible. If your combination sum output is missing every repeated-element answer, this is why.

Dropping the start index in subsets. You get every permutation of every subset, so the answer count jumps from 8 to 16 on three items, and the duplicates aren't obvious at a glance.

Checking the total only at the leaves is correct, and slow, since the whole point is to reject as early as the rules allow.

Assuming the prune still holds with negative candidates. If a candidate can be negative, exceeding the target no longer means the branch is dead, since a later negative can bring the sum back. The prune quietly becomes wrong. Check the constraints before you rely on it.

Check yourself