0
Challenge · 46Recursion & Backtracking
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.
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