Quiz
Warm-up from lesson 5-1: every recursive function needs a base case and a recursive case that shrinks the problem. In the recursion TREE from lesson 5-2, what did each node represent?
Backtracking: explore, then undo
Some problems ask for every combination: all subsets, all permutations, all valid boards. The tool is backtracking, and the mental model is walking a decision tree:
- At each step you face a choice (include element i, or not?).
- Choose one option, then recurse deeper.
- When you return, undo the choice and try the next option.
Choose → explore → un-choose. The undo is the defining move: it restores the shared state (path) so the next branch starts clean.
A subset decision tree for [1, 2, 3] has one level per element, each with two branches: in or out. Its 2×2×2 = 8 leaves are exactly the 8 subsets.
Code exercise · python
Run this. explore(i) decides element i both ways. Note the exact choose / explore / undo shape: append, recurse, pop, recurse.
Quiz
In subsets, why does the code append path[:] (a copy) instead of path itself?
Code exercise · python
Your turn. Count the subsets of nums whose sum equals target. Same skeleton as subsets, but carry a running total instead of a path, and count instead of collecting.
Problem
A set has 5 elements. How many subsets does it have in total (including the empty set)?