Study notes · 9% of the exam

Recursion, Backtracking and Divide and Conquer

Recursion solves a problem through smaller copies of itself; backtracking builds candidate solutions one choice at a time and undoes each choice after exploring it. Know how to trace call order, count the results an enumeration produces, prune safely, and spot the shared-state bugs interviewers love.

Key points

1
Every recursive function needs a base case, and every call must move toward it. CPython has no tail-call optimisation and a default recursion limit of 1000, so very deep recursion should become a loop or an explicit stack.
2
Code before the recursive call runs on the way down (pre-order); code after it runs while the stack unwinds (post-order). Trace small inputs by hand to get print orders right.
3
The backtracking template is choose → explore → un-choose. Record a copy of the path (path[:]) at each leaf, and undo every change (pop, unmark, swap back) before the next choice.
4
Know the output sizes: 2ⁿ subsets, n! permutations, C(n, k) combinations, the nth Catalan number of balanced parentheses strings. Enumeration can never beat the size of its output.
5
Prune only branches that provably can't lead to an answer: break when a sorted candidate exceeds the remaining target, and skip equal values at the same depth (i > start) to avoid duplicate results.
6
Divide and conquer splits the input, solves the parts and combines them: T(n) = 2T(n/2) + O(n) gives O(n log n) (merge sort, closest pair), while one half-size call per level gives O(log n) (fast exponentiation).
7
Memoisation helps only when subproblems repeat (naive Fibonacci makes 177 calls for fib(10)); it doesn't speed up enumerating distinct outputs such as permutations.

Common traps

res.append(path) stores a reference to the one shared list, so every result ends up identical (usually empty). Append path[:].
Mutable default arguments (def f(n, acc=[])) are created once and shared across calls, so results leak between top-level calls.
Forgetting to undo a change (restore a grid cell, swap back, pop) silently corrupts later branches: you get duplicates, missing answers or false negatives without any error.

Read the source

Test yourself on Recursion, Backtracking and Divide and Conquer

Ten questions, with the answer and explanation after each one.