Each node represented one function call, and its children were the calls that call made.
Each edge means "this call made that call", so a path from the root down to a node is the chain of pending calls, which is exactly the call stack at that moment.
Backtracking, this unit's topic, is recursion where the tree is a tree of decisions rather than of subproblem sizes, and where the goal is deliberately to walk all of it.
That shift changes what the leaves mean. In fib a leaf was a base case returning a number, and here a leaf is a complete candidate answer.
Keep the tree picture in your head, because it is the whole mental model for the next four lessons.
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, such as whether to include element i.
- Choose one option, then recurse deeper.
- When you return, undo the choice and try the next option.
Choose, explore, then un-choose. The undo is the defining move, because it restores the shared state, usually a list called path, so the next branch starts clean.
Without the undo, choices from one branch leak into the next and every answer after the first is wrong.
A subset decision tree for [1, 2, 3] has one level per element, each with two branches for in or out. Its 2 × 2 × 2 = 8 leaves are exactly the 8 subsets.
That count is also the warning. The tree size is the answer size, so backtracking is only viable when the number of answers is manageable.
All subsets
explore(i) decides element i both ways.
def subsets(nums): result = [] path = [] def explore(i): if i == len(nums): result.append(path[:]) return path.append(nums[i]) explore(i + 1) path.pop() explore(i + 1) explore(0) return result for s in subsets([1, 2, 3]): print(s)
Output
[1, 2, 3] [1, 2] [1, 3] [1] [2, 3] [2] [3] []
The choose, explore, un-choose shape is the four middle lines: append, recurse, pop, recurse. The pop sits between the two recursive calls, which is what makes the second one see a path without nums[i].
The base case is i == len(nums), meaning every element has been decided. Nothing is checked or filtered, so every leaf is a valid answer.
path[:] snapshots the current contents, and the next block explains why the copy is mandatory.
The output order follows the tree. The take branch comes first at every level, so the full set prints first and the empty set prints last, which is depth-first order rather than anything sorted.
The eight results are the eight subsets, and path was a single list throughout, mutated 14 times and never copied except at the leaves.
Because path keeps changing as the recursion continues, so storing the list itself would fill result with references to one shared list that is empty by the end.
There is one path object, and every branch mutates it through append and pop. Appending path stores a reference to that object rather than its contents.
By the time subsets returns, every pop has run and path is empty, so result would print as eight empty lists.
path[:] makes a shallow copy, freezing the contents at that moment. list(path) and path.copy() do the same thing.
Forgetting this copy is the single most common backtracking bug in interviews, and it is easy to spot once you know the symptom: the right number of answers, all of them identical or empty.
The cost is real but acceptable. Each leaf copies up to n elements, which is why generating all subsets is O(n · 2ⁿ) rather than O(2ⁿ).
Counting subsets that hit a target
The same skeleton, carrying a running total instead of a path.
def count_sum_subsets(nums, target): count = 0 def explore(i, total): nonlocal count if i == len(nums): if total == target: count += 1 return explore(i + 1, total + nums[i]) explore(i + 1, total) explore(0, 0) return count print(count_sum_subsets([2, 4, 6, 10], 16)) print(count_sum_subsets([1, 2, 3], 6))
Output
2 1
No undo is needed here, which is the point worth extracting. total is passed as an argument, so each branch gets its own value automatically, and undo is only necessary for shared mutable state like path.
Passing state down rather than mutating it is often the cleaner choice, and it is why the recursive case is two plain calls with no bookkeeping between them.
The base case now filters. Every leaf is reached, and only the ones whose total matches the target are counted.
nonlocal count lets the inner function modify the outer variable rather than creating a new local one. Without it, count += 1 would raise an UnboundLocalError.
The two subsets of [2, 4, 6, 10] summing to 16 are {2, 4, 10} and {6, 10}, and for [1, 2, 3] only the full set reaches 6.
This still visits all 2ⁿ leaves. Unit 9 solves the same question with dynamic programming in O(n · target), which is the difference between enumerating answers and counting them.
A 5-element set has 2⁵ = 32 subsets, including the empty set.
Each element is an independent in-or-out decision, so the count multiplies by 2 per element, which is exactly why the decision tree doubles per level.
The empty set and the full set are both included, which is the convention interview problems use unless they say otherwise.
The number is also a warning about scale. Subset backtracking is O(2ⁿ), which is fine for n around 20 at a million leaves, and hopeless at n = 100, where 2¹⁰⁰ is larger than the number of atoms in a fair-sized object.
Knowing that boundary is part of the interview answer. If n can be large, the problem is not asking you to enumerate, and the intended solution is dynamic programming or a greedy argument instead.