0

Recursion as a decision tree

Recursionused in ~95% of apps

You have used recursion on trees, where the tree was handed to you. Now you build the tree yourself out of choices, and every problem in this tier is a walk through it.

Core idea. When a problem is a series of decisions, the possibilities form a tree. Each level is one decision, each branch is one option, and each leaf is one complete answer. Walking that tree is recursion, and because you reuse a single path as you walk, every choice you make on the way down has to be unmade on the way back up.
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