Week 9: Backtracking

Pattern family: Backtracking · Time budget: 13 hours · Prerequisites: Weeks 1 through 8 done, with recursion (Week 7), the path append/pop discipline, list copying (path[:]), and the 2-D list aliasing trap from the refresher fresh. · Cold-revisit obligation: Koko Eating Bananas, Maximum Depth of Binary Tree.

Overview

Backtracking is one disciplined loop applied over and over: at each step you make a choice, recurse to extend it, then undo the choice so the next option starts from a clean slate. That last beat is the whole pattern. Most people can write the make-choice and recurse parts on instinct from Week 7 recursion; the bug that costs them the problem is forgetting to undo, so a choice from one branch leaks into the next. Backtracking is a systematic walk over a tree of partial solutions, and the undo is what lets a single shared path list stand in for that entire tree without copying it at every node.

The exponential cost is real and expected: subsets are O(2^n), permutations O(n!), and you do not apologize for it because the problem genuinely asks for every arrangement. What you do instead is prune. The moment a partial solution cannot possibly lead to a valid full one, you stop and back out rather than finishing a doomed branch. Most of this week is training the move that fires before any code: when the problem says “generate all”, “find every”, or “place these without conflict”, reach for the make-choice / recurse / undo skeleton and ask immediately where you can prune.

flowchart TD
    Q["Read the problem"] --> A{"Does it ask for ALL<br/>subsets / permutations /<br/>combinations, or EVERY<br/>placement satisfying X?"}
    A -->|yes| B{"Can I build a solution<br/>one choice at a time,<br/>and undo each choice?"}
    A -->|no| G["Probably a single pass, DP,<br/>or a different pattern.<br/>Keep reading the cues."]
    B -->|yes| H["Backtracking: make a choice,<br/>recurse, undo the choice.<br/>Prune dead branches early."]
    B -->|"I only need one number (a count or a best value)"| W["You may not need the full tree.<br/>Consider DP (Weeks 13-14) instead."]

Notice: the decision happens before you code, and it has two beats. First, does the problem want every arrangement (not just one number)? Second, can you build it one reversible choice at a time? Naming the pattern out loud (principle 1) is what makes this diagram fire under pressure.

Warm-Up: Retrieve Before You Begin

Answer from memory, no peeking. This pulls forward the prior-week tools that backtracking leans on hardest.

  1. From Week 7 and the refresher: what are the two parts of any recursive function (the part that stops, and the part that shrinks the problem), and why does a missing or wrong stopping part cause infinite recursion?
  2. From the refresher: what does path[:] produce, and why does results.append(path) (without the slice) store something different from results.append(path[:])?
  3. From the refresher: why does grid = [[0] * cols] * rows create a trap, and what is the correct way to build an independent grid of rows?
Check your recall 1. Every recursion has a base case (the condition under which it returns immediately without recursing) and a recursive case (which does a little work and calls itself on a strictly smaller or closer-to-base subproblem). If the base case is missing or never reached, the calls never stop and you hit `RecursionError`. In backtracking the base case is usually "the partial solution is complete, record it" or "this branch is dead, return". 2. `path[:]` produces a new list with the same elements: a shallow copy, a snapshot of `path` at this instant. `results.append(path)` stores a reference to the one shared `path` list, so when you later `append` and `pop` to explore other branches, the stored entry changes with it and you end up with a list of identical (often empty) lists. `results.append(path[:])` stores an independent snapshot that no later mutation can touch. This single distinction is the most common backtracking bug. 3. `[[0] * cols] * rows` makes `rows` references to the *same* inner list, so writing `grid[0][0] = 1` changes every row at once. Build rows independently with a comprehension: `grid = [[0] * cols for _ in range(rows)]`. This matters in Word Search and any time you carry a 2-D visited grid.

Learning objectives

By the end of this week you can:

  • Recognize the “generate all / find every / place without conflict” cue and reach for the make-choice / recurse / undo skeleton without being told.
  • Construct a backtracking solution from the three-beat skeleton, with a correct base case and a correctly restored shared path.
  • Distinguish the start-index template (subsets, combinations, where order does not matter) from the used-set template (permutations, where every position can draw any unused element).
  • Apply pruning to cut dead branches early, and explain why pruning lowers the constant without changing the worst-case big-O.
  • Analyze the time and space complexity from the size of the solution tree (how many nodes, how much work per node) and name what dominates at scale.
  • Defend every line of each solution you commit, from memory, with no AI open, including exactly where each choice is undone.

Recognition cue

“Generate all subsets, permutations, or combinations”, “find every solution that satisfies X”, and placement problems like N-Queens almost always mean backtracking. The surface phrases are “all”, “every”, “list each”, and “how many ways can I arrange / place”. The deeper tell is that a solution is built incrementally from a sequence of choices, and that you need to explore every combination of those choices rather than compute a single aggregate. If you only need one number (a count, a maximum), pause: that is often dynamic programming (Weeks 13 and 14), which counts or optimizes without enumerating every arrangement.

Core concepts to internalize this week

  • The make-choice / recurse / undo-choice skeleton. This is the entire pattern. Pick an option, add it to path, recurse to extend the partial solution, then remove it from path before trying the next option. The undo (the “backtrack”) is what makes the single shared path correct: after you return from a branch, path is exactly what it was before you entered it.
  • Base case: record or stop. A backtracking recursion ends in one of two ways. Either the partial solution is complete (place it in results, usually as path[:]), or the branch is dead (a conflict, an overshoot) and you return without recording. Getting the base case right is half the battle.
  • The start-index template (order does not matter). For subsets and combinations, each element is either in or out, and [1, 2] and [2, 1] are the same set. Pass a start index and only ever look forward from it, so you never revisit an earlier element and never produce a reordering of a set you already built.
  • The used-set template (order matters). For permutations, every position can hold any element not yet placed, and [1, 2] and [2, 1] are different answers. Track which elements are used (a boolean list or a set) instead of a start index, so each recursive call can choose any remaining element.
  • Pruning. The point of backtracking is to not explore branches that cannot work. In Combination Sum, once the remaining target goes negative you stop. In N-Queens, you never even place a queen on a threatened square. Pruning does not change the worst case (a problem with no conflicts still explores everything), but on real inputs it can turn an intractable search into an instant one. It is a constant-factor win that is often enormous.
  • Reuse vs no-reuse, encoded in the recursive index. Whether you may use an element again is decided by what index you pass to the recursive call. Recurse with i + 1 (advance past the current element) for “use each at most once”; recurse with i (stay) for “reuse allowed”, as in Combination Sum. One character is the whole difference.
  • Backtracking on a grid. Word Search walks a board, marking a cell as visited before recursing into its four neighbors and unmarking it on the way out. The “mark, recurse, unmark” rhythm is the same skeleton; the only twist is that the choice is a move on a grid and the undo restores the cell.

Common misconception. “I built the solution and it explores every branch, so it is correct.” Reality. If you forget to undo the choice (the path.pop(), the unmark), the next branch starts contaminated by the previous one, and you get wrong answers, not just slow ones. Equally, results.append(path) instead of results.append(path[:]) stores a live reference to the one shared list, so every recorded “solution” is really the same list and ends up identical (often empty) once the search unwinds. Make-choice, recurse, undo, and snapshot with path[:]. The undo and the copy are the two lines beginners drop, and they are exactly the two lines that make the pattern work.

Heavy concept ahead. The three-beat skeleton is the load-bearing idea of this week, so internalize it deliberately, in this order, every time:

  1. Base case. Is this partial solution complete (record path[:]) or dead (return)?
  2. Make a choice. Add an option to path (and mark it used, if order matters).
  3. Recurse. Extend the partial solution with the choice in place.
  4. Undo the choice. Remove the option from path (and unmark it) so the next option starts clean. Write these beats down, in words, for every problem this week before you write any code. The Pattern Card asks for them; the canonical deep-dive walks them; the debrief checks them. Skipping the undo is the single most common way backtracking solutions come out wrong.

Python idioms this week

You are not yet expected to be fluent, so here is the toolbox this week uses. If any is unfamiliar, open the Python refresher before Monday. The sections you want are recursion (Section 10), the list append/pop and path[:] copy (Section 3), sets (Section 6), tuples as grid keys (Section 4), and the 2-D aliasing pitfall (Section 13).

  • Recursion with a nested helper that closes over a shared path and a results list (recursion, Section 10).
  • path.append(x) to make a choice and path.pop() to undo it; the pair always brackets the recursive call.
  • results.append(path[:]) (or list(path)) to store an independent snapshot, never the live path.
  • A set or a boolean list for “used” elements (permutations), and set membership for O(1) conflict checks (N-Queens columns and diagonals).
  • A tuple (r, c) as a grid coordinate, hashable for a visited set.
  • 2-D grids built correctly as [[v] * cols for _ in range(rows)], never [[v] * cols] * rows.

These are tools you are allowed to know cold in an interview. The pattern (the skeleton, where to prune, what to undo) is the part you build yourself.

Pattern Card requirement

Before you solve the canonical problem, write your Pattern Card at .tutor/pattern-cards/backtracking.md. It must contain:

  • The recognition cue, in your own words.
  • The algorithmic skeleton in pseudocode (the make-choice / recurse / undo template you can reuse, with the base case and the prune point marked).
  • Time and space complexity, general form (the size of the solution tree times the work per node; plus the O(depth) recursion-stack space).
  • Three edge cases (empty input, a single element, and an input with duplicates or no valid placement are good starts).
  • One war story (a bug you actually hit this week); fill this in at the end of the week.

The first four sections must be present before you start the canonical deep-dive. The tutor will probe the card; it will not write any of it for you.

Canonical deep-dive

Problem: N-Queens (https://leetcode.com/problems/n-queens/)

N-Queens is this course’s home for the make-choice / recurse / undo skeleton and for pruning done right. The full guided walk-through, with the one-queen-per-row insight, the column-and-two-diagonals conflict sets, and the exact complexity, is in canonical/n-queens.md. Work it there. You will implement it yourself, in your own work repo, and write a short debrief. The walk-through is deliberately not an answer key: it shows you how to think, and stops short of code you could paste.

Practice set

Four problems, in this order. Each has its own folder under practice/ with the problem link, a complexity target for you to fill in, and the debrief template. Do not skip ahead.

  1. Subsets (practice/subsets/). The cleanest backtracking problem: at every element, choose in or out. This is where the start-index template and the path[:] snapshot become muscle memory.
  2. Combination Sum (practice/combination-sum/). Combinations with reuse and a target. Teaches the prune (stop when the remaining target goes negative) and the “recurse with i, not i + 1” reuse trick.
  3. Permutations (practice/permutations/). Order now matters, so the start index gives way to a used marker. This is the contrast that makes both templates click.
  4. Word Search (practice/word-search/). Backtracking on a grid: mark a cell, recurse into its neighbors, unmark on the way out. The skeleton, applied to a board instead of a list.

Each problem follows the five-beat rhythm.

The five-beat rhythm (every problem)

  1. Pattern Card is written (you did this Monday).
  2. Name the pattern aloud and write your approach as a plain-English comment before any code.
  3. Struggle floor: 25 minutes unaided.
  4. Hint ladder if needed: six rungs, one per ask.
  5. Debrief: the five questions, in your commit message, before the next problem.

Reflect

Ten minutes in your notebook, in writing:

  • Explain it back: describe the make-choice / recurse / undo skeleton to a peer who has only done arrays and trees so far, in three sentences, and say what breaks if the undo is dropped.
  • Connect: Subsets uses a start index and Permutations uses a used marker. In one sentence each, why does “order does not matter” lead to start and “order matters” lead to used?
  • Monitor: which is still fuzzy, the base case (when to record vs return) or the undo (what exactly to restore)? Write the one sentence that would clear it up.

Knowledge Check

Answer from memory first. Items marked ⟲ are spaced callbacks to earlier material.

  1. State the make-choice / recurse / undo skeleton in your own words, and name the base case (the two ways a branch ends).
  2. For N-Queens, what three sets give O(1) conflict checks, and what is the key for each of the two diagonal families?
  3. In Combination Sum you recurse with the same index i rather than i + 1. What does that one choice encode, and how would it differ for a “use each element at most once” problem?
  4. ⟲ From Week 7 and the refresher: why must a backtracking recursion store path[:] rather than path when it records a solution, and what symptom do you see if you get this wrong?
  5. ⟲ From the refresher: why does [[0] * cols] * rows create a 2-D grid that misbehaves, and what is the correct construction?
Answer key 1. At each step: make a choice (add an option to `path`), recurse to extend the partial solution with that choice in place, then undo the choice (remove it from `path`) before trying the next option. A branch ends either because the partial solution is complete (record a snapshot `path[:]` in `results`) or because it is dead, for example a conflict or an overshoot (return without recording). 2. A set of threatened columns, a set for the `r - c` diagonal family, and a set for the `r + c` diagonal family. Every square on one "down-right" diagonal shares the same value of `r - c`; every square on one "down-left" diagonal shares the same value of `r + c`. Checking membership in three sets is O(1), versus scanning the board. 3. Recursing with `i` lets the same element be chosen again, which is exactly "a coin / candidate may be reused any number of times". For "use each element at most once" you recurse with `i + 1`, advancing past the current element so no branch can pick it twice. 4. `path` is one shared, mutating list; `results.append(path)` stores a reference to it, so when the search unwinds (the `pop`s run), every stored entry changes with it and you end up with a list of identical lists, usually all empty. `path[:]` stores an independent snapshot taken at that instant, which no later mutation can touch. The symptom is a result list of the right length but full of duplicated or empty lists. 5. `[[0] * cols] * rows` makes `rows` references to the *same* inner list, so `grid[0][0] = 1` changes every row at once. Build the rows independently: `grid = [[0] * cols for _ in range(rows)]`.

Cold revisit

This Friday, before any new work, re-solve two prior problems cold: no notes, no prior code open, no AI, the standard 25-minute floor on each. The full instructions are in revisit.md.

  1. Koko Eating Bananas (Week 5, Binary Search). A blind re-solve. Do not look at which pattern it is until you have named it yourself; recognizing it cold is the point.
  2. Maximum Depth of Binary Tree (Week 7, Trees). A blind re-solve, same rules.

Neither is a backtracking problem, and that is deliberate: the cold revisit trains recognition across the whole course, not just this week’s pattern. Debrief each at the end and log the outcome in .tutor/revisit-log.md.

How to know you are done with this week

  • Pattern Card complete at .tutor/pattern-cards/backtracking.md, including the war-story field.
  • Canonical deep-dive done: N-Queens implemented yourself, with the column-and-diagonal conflict sets and a correct undo, plus your short debrief (in your work repo).
  • Four practice problems solved, each with a five-question debrief in its commit message.
  • .tutor/revisit-log.md updated by the tutor with this week’s problems and the two cold revisits, with dates.
  • .tutor/progress.md updated to “Week 9 complete; ready for Week 10.”

If any of the above is missing, the week is not done. The tutor will not advance you to Week 10 until all five are present.

Resources

Free, no account required:

  • [Article] Backtracking, the idea: https://en.wikipedia.org/wiki/Backtracking
  • [Article] Eight queens puzzle: https://en.wikipedia.org/wiki/Eight_queens_puzzle
  • [Docs] Python recursion and functools (for context on recursion limits): https://docs.python.org/3/library/functools.html
  • [Docs] Python list (append, pop, slicing for copies): https://docs.python.org/3/tutorial/datastructures.html

Table of contents