0
Challenge · 47Recursion & Backtracking
Subsets
Recursionused in ~85% of apps
The first real backtracking problem, and the one whose shape the next three borrow. Two ways to write it, and the second one generalises to almost everything else in the tier.
Core idea. A subset is a series of take-or-leave decisions, so the possibilities double with every item. Written as a loop over a starting position rather than as a take-or-leave pair, the same code produces subsets of a fixed size, combinations, and every problem where order does not matter.
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
every subset of [1, 2, 3], one move at a time
the path you are holding
empty
recordrecord a copy of []
move 0 of 22adds 0 · undos 0
answers recorded so far
[]
Count the adds and the undos as you go. They always end up equal, and that is what backtracking means.
↑ play a little first, then dig in