0

Combination sum and pruning

Recursionused in ~75% of apps

The idea that makes backtracking usable. A branch you can prove will fail costs nothing if you never walk down it, and one well placed check often turns a solution that times out into one that finishes instantly.

Core idea. Pruning means abandoning a branch the moment it cannot possibly succeed, rather than exploring it and discovering that at the bottom. It needs an argument, not a guess: you must be certain that nothing below can work. Sorting first is what usually makes that certainty available.
Playground, this isn't a screenshot
target 7 from [2, 3, 6, 7], with branches cut early
the path you are holding
2
addadd 2, 5 left to make
move 0 of 27adds 0 · undos 0
answers recorded so far
nothing yet

A cut branch is work you never do. That is the only thing separating a solution that finishes from one that does not.

↑ play a little first, then dig in