Subset sum
Backtracking tries choices one at a time and undoes them when they lead nowhere. For each value, first try including it, and if that fails, try leaving it out. Because all values are positive, overshooting the target means that whole line of choices can be abandoned at once.
38427
chosen values (still need 10)
Pick some of these values that add up to exactly 10. Try each value both ways, in and out, and back out of dead ends.
1function subsetSum(a, target, i = 0, chosen = []) {2 if (target === 0) return chosen;3 if (i === a.length || target < 0) return null;4 chosen.push(a[i]);5 const withIt = subsetSum(a, target - a[i], i + 1, chosen);6 if (withIt) return withIt;7 chosen.pop();8 return subsetSum(a, target, i + 1, chosen);9}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | n | the first values tried add up straight away |
| average | 2ⁿ | many choices get tried and undone |
| worst | 2ⁿ | no subset works, so every combination is ruled out |
| space | n | the recursion depth and the chosen list |
Where it breaks
- Exponential time. Each value is in or out, so n values give 2ⁿ combinations. Pick Impossible: nothing makes 9 from 4, 6 and 8, so every branch must be tried before the answer is no.
- Pruning only works for positive values. Stopping as soon as the total overshoots is safe because adding more can only make it bigger. With negative values, an overshoot could still come back down.
- Small totals have a faster method. If the target is small, dynamic programming checks every reachable total once, in n × target steps instead of 2ⁿ.