0
Challenge · 49Recursion & Backtracking
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.
poke it, drag it,
try to break it
try to break it
no slides here.
you drive.
you drive.
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