0

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.
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