Coding Interview: Patterns & DSA · Recursion, Backtracking & DP · Lesson 1 of 3
Recursion & backtracking
Recursion solves a problem in terms of smaller instances of itself. Every recursion needs a base case (when to stop) and a recursive case (how to shrink the problem). Backtracking is recursion that builds candidates incrementally and undoes a choice when it leads nowhere — used to enumerate subsets, permutations, and constraint solutions.
def subsets(nums): res, path = [], [] def backtrack(start): res.append(path[:]) # record the current subset for i in range(start, len(nums)): path.append(nums[i]) # choose backtrack(i + 1) # explore path.pop() # un-choose (backtrack) backtrack(0) return res
- Choose → explore → un-choose is the backtracking skeleton. The
path.pop()restores state for the next branch. - Prune early: abandon a partial candidate the instant it cannot lead to a valid answer (the difference between fast and exponential).
- Backtracking explores a decision tree; its cost is often
O(2^n)(subsets) orO(n!)(permutations) — inherent to enumerating all of them.
Recognize itBacktracking is the tell for problems asking for all combinations / permutations / subsets, N-Queens, Sudoku, word search, and generating valid parentheses — 'find every way to...'.
Copy when you recordAppend a copy (
path[:]), not path itself. Otherwise every result points at the same list that keeps mutating, and you end up with a list of identical (usually empty) results.◆ Lock it in
- Recursion needs a base case and a shrinking recursive case.
- Backtracking = choose, explore, un-choose; prune dead branches early.
- Record a copy of the path, and expect
O(2^n)orO(n!)for full enumeration.
Feynman drill — say it out loudExplain the choose/explore/un-choose loop and why you must copy the path before recording it.
Step 1 rate your confidence · Step 2 pick your answer
The defining move that makes an algorithm 'backtracking' rather than plain recursion is:
Step 1 — how sure are you?