Backtracking Pattern — the undo-step that trips candidates

Backtracking is a recursive search where you try a choice, explore it, and undo if the path fails. The interview test is naming the menu of choices at each level — not whether you can write a recursive call.

Here's a thing I've seen happen in maybe forty mock interviews over the last year, and it's always the same: the candidate reads a backtracking problem, panics for a second, says "okay, it's DFS with undo," writes def backtrack(...), and then stares at the parameters for thirty seconds because they don't know what to put inside them.

That pause — the one where you're staring at an empty parameter list — is the real bug. It's not that recursion is confusing. It's that nobody told you what decision you're making at each level of the tree, so you can't name the state that tracks it.

I'm going to give you a different framing than the one you've probably seen. The "choose / explore / un-choose" template you've read in every backtracking post is not wrong exactly, but it's the answer after you've already solved the hard part. The hard part is upstream, and it's the part that makes candidates freeze.

The One Question

When you see a problem that smells like backtracking — permutations, subsets, combinations, N-Queens, sudoku, word search — stop trying to remember a template. Ask yourself this:

At each level of the recursion, what menu of choices am I picking from?

That's it. That single question is the load-bearing insight. If you can write down "at level k of the recursion, I'm picking one item from the set S," then you know exactly what parameters your recursive function needs, what your base case is, and what your "undo" step looks like.

Let me prove that. Here are four classic backtracking problems. Each one gets a different answer to "what's the menu?":

Notice how different those menus are. "Choose / explore / un-choose" is the same three-beat rhythm for all of them, but the thing you're choosing from is completely different. And that's what you actually have to figure out when you sit down with a new problem. The template is the easy part. Naming the menu is the whole game. labuladong's framework covers this same three-family split and explains the menu-shape differences with explicit code for each.

Why "DFS With Undo" Is Not Enough

Let me show you what goes wrong when you lead with the template instead of the menu.

Here's a candidate solving "generate all permutations of nums = [1,2,3]" in a mock interview. They start with:

PYTHON

Copy

def permute(nums): result = [] def backtrack(current): if len(current) == len(nums): result.append(current[:]) return for num in nums: # ← the bug lives here current.append(num) backtrack(current) current.pop() backtrack([]) return result

This looks right. It matches the template. It even runs. But it produces [1,1,1], [1,1,2], [1,1,3], ... — every length-3 string over the alphabet {1,2,3}, which is not what permutations means.

The bug is in the for num in nums line. The candidate wrote "iterate over everything" instead of "iterate over the menu at this level." The menu for permutations is unused elements, not all elements. And the reason the candidate got it wrong is that they never asked the menu question. They just reached for the template.

The fix is to track which elements are still on the menu:

PYTHON

Copy

def permute(nums): result = [] def backtrack(current, used): if len(current) == len(nums): result.append(current[:]) return for i in range(len(nums)): if used[i]: continue # ← not on the menu anymore used[i] = True current.append(nums[i]) backtrack(current, used) current.pop() used[i] = False backtrack([], [False] * len(nums)) return result

Once you see that used is literally "what's still on the menu," the parameter list stops being a staring contest. You needed used because the menu shrinks as you descend. The template didn't tell you that. The menu question did. NeetCode's permutations walkthrough covers this same used-set pattern in video form if you want a second angle on it.

The Recursion Tree, Labeled

Here's what the permutations search tree actually looks like. I'm going to label every edge with which choice from the menu, because that's the thing that goes missing when you only draw the nodes:

Diagram

Copy source

Rendering diagram...

(Drawn for n = 2 so it fits on one screen. For n = 3 the tree is structurally identical — the root has three branches instead of two, each subtree has two leaves instead of one, and you end up with n! = 6 leaves total.)

Every edge is labeled with the decision made at that step. Every node has both the partial state and the remaining menu. The "un-choose" step is what happens when you return from a child: you put the element back on the menu.

If you draw this tree before writing code, you cannot write the wrong recursion. The tree is the code. You're just translating it.

A Second Worked Example: Subsets

Subsets has a different menu. At each level, you're not picking "which element comes next" — you're picking "include or exclude the element at position i." That's a menu of size two, every time, for n levels.

PYTHON

Copy

def subsets(nums): result = [] def backtrack(i, current): if i == len(nums): result.append(current[:]) return # Menu option 1: exclude nums[i] backtrack(i + 1, current) # Menu option 2: include nums[i] current.append(nums[i]) backtrack(i + 1, current) current.pop() backtrack(0, []) return result

The menu is exactly two choices, so the "for loop" from the permutations version collapses into two separate recursive calls. Same template — still choose / explore / un-choose — but a completely different menu shape. You could not have written this from the template alone. You had to know the menu first.

Diagram

Copy source

Rendering diagram...

(Drawn for n = 2 so it fits on one screen. For n = 3 every leaf would fan out once more — 8 leaves instead of 4 — but the branching factor stays fixed at 2 per level, which is the whole teaching point.)

A Third Worked Example: N-Queens

Now the menu gets interesting. For N-Queens, at each row you're placing one queen. The menu at row r is "the columns that aren't attacked by any queen placed so far."

This is the first problem where the menu itself is computed — it's not a static list, it's a function of your current state. And that's where most candidates bail out, because they confuse "pruning" with "the menu."

They are the same thing. Pruning is the menu-narrowing step. When you skip column c because "queen in row 2 already attacks column c," you are not pruning some secondary search. You are saying "column c was never on the menu at this level in the first place."

PYTHON

Copy

def solve_n_queens(n): result = [] cols = set() diag1 = set() # row - col diag2 = set() # row + col def backtrack(row, placement): if row == n: result.append(placement[:]) return for col in range(n): if col in cols or (row - col) in diag1 or (row + col) in diag2: continue # not on the menu at this row cols.add(col) diag1.add(row - col) diag2.add(row + col) placement.append(col) backtrack(row + 1, placement) placement.pop() cols.remove(col) diag1.remove(row - col) diag2.remove(row + col) backtrack(0, []) return result

Read the loop body. The continue is the menu. The three set operations are how you mutate what the menu will look like one level down. Every single thing in this function is either "check the menu," "commit to a choice," "recurse," or "undo the choice." The template didn't change. The menu did. The canonical LeetCode backtracking post shows this same unified template applied across six different problems — once you see the pattern, the only variable between them is the menu definition.

Donald Knuth, writing about exact cover problems in the Dancing Links paper (2000), put this very cleanly: the hard part of backtracking isn't the search, it's representing the state so that the menu at each level is cheap to compute and cheap to undo. Knuth built an entire data structure (dancing links) just to make the menu-update step O(1). That's how load-bearing the menu is. A famous computer scientist wrote a paper about it.

When To Prune (The Other Menu Question)

Once you've named the menu, there's a second question that separates the 7/12 answers from the 11/12 answers in a real interview: when can you remove something from the menu early?

This is pruning, and it's what Jeff Erickson's free algorithms textbook (chapter 2, University of Illinois, the standard academic reference) calls the entire difference between "brute force enumeration" and "real backtracking." Brute force also has a menu. Backtracking is brute force plus pruning.

A good prune has two properties (algo.monster's pruning breakdown covers these conditions with worked examples):

1. It's sound — removing the item from the menu cannot eliminate any correct answer.
2. It's cheap — checking whether to prune is much faster than actually exploring the subtree.

For N-Queens, the column-plus-diagonal check is sound (a queen in an attacked column cannot extend to a valid placement) and cheap (three set lookups). For a subset-sum problem with a target k, "if the current sum already exceeds k, stop" is sound (sums only grow) and cheap (one comparison). These are the good prunes.

The bad prune — the one that loses you points in an interview — is saying "I'll sort the input first and then prune," without being able to articulate why the sort makes the prune sound. If you can't defend the soundness of your prune, don't use it. An interviewer watching you prune something they can't verify is going to stop trusting your reasoning.

The Three Families At A Glance

Every backtracking problem you'll see in an interview is a variation of one of three families. They share the template but differ in menu shape, branching factor, and base case. Here's the map:

Diagram

Copy source

Rendering diagram...

If you can identify which family a problem belongs to in the first 30 seconds, you know the menu shape before you write a single line. That's the 11/12 move.

The Interview Talk-Track

Here's how to narrate a backtracking problem out loud so an interviewer can follow what you're doing. You're not showing off — you're making your thinking legible, which is the actual signal senior interviewers grade on.

1. Name the menu. "At each level of the recursion, I'm picking one of the unused elements from the input. So my state needs to track which elements are used."
2. Name the terminal condition. "A branch terminates when my partial result has length n, at which point I copy it into the results list."
3. Name the prune, if any. "I can prune any branch where the partial sum already exceeds the target, because adding more elements can only increase it."
4. Write the function. With the first three nailed down, the function signature and body are mechanical. You're not thinking at this point, you're transcribing.
5. Walk the small case. Pick n=3 and walk the tree out loud. This catches off-by-ones and shows the interviewer you can debug by reading code, not by running it.

If you do those five things in that order, you will not freeze up. The freezing happens specifically because step 1 is skipped — candidates jump straight to step 4 and then wonder why they can't figure out the parameters.

Common Failure Modes (With Fixes)

These are the bugs I see over and over in coaching sessions. If you can recognize them in your own code, you can fix them without panicking.

Failure 1: Shared mutable state that isn't copied on append

PYTHON

Copy

if is_terminal(): result.append(current) # ← bug: appends a reference

When the recursion unwinds and mutates current, every reference in result also mutates. The fix is result.append(current[:]) or result.append(list(current)). This is the single most common backtracking bug in mock interviews. Save yourself an interview: make it muscle memory.

Failure 2: Choose / explore / un-choose in the wrong order

PYTHON

Copy

backtrack(current) # explore before choose — wrong current.append(num) current.pop()

The recursive call has to happen while the choice is committed, not before and not after. Choose, then recurse, then un-choose. Always in that order.

Failure 3: "I'll use a visited set" when the menu is positional

For subsets and combinations, the menu is "elements at position ≥ i" — a positional menu. Candidates sometimes reach for a visited set out of habit, when all they actually need is to pass i+1 into the recursive call. Adding a visited set is not wrong, but it's extra state that makes the function harder to reason about and slower. Choose the cheapest representation of the menu that's still correct.

Failure 4: Not realizing when backtracking is overkill

Some problems look like backtracking but have cleaner solutions. "Generate parentheses" feels like backtracking, and one clean solution is backtracking. "Sum of subset" also feels like backtracking, but for large inputs it's actually DP. If the state space has heavy overlap — the same sub-problem showing up in many branches — you want memoization, and at that point you're doing DP, not backtracking. The menu question still applies, but the implementation changes. Know where the boundary is.

Citations and Further Reading

If you want to go deeper than interview-prep depth, these three references are the canonical ones:

• Jeff Erickson, Algorithms (free textbook, University of Illinois), Chapter 2: Backtracking. The academic reference. Free online at jeffe.cs.illinois.edu/teaching/algorithms. Erickson's framing of "choose from the candidate set, recurse, uncommit" is the direct ancestor of what I'm calling "name the menu."
• Donald Knuth, "Dancing Links" (2000). arXiv:cs/0011047. Knuth's paper on exact cover problems. If you want to see someone treat the menu-update step as the performance-critical part of backtracking and build a data structure around it, this is the paper.
• Hello Interview, "Recursion and Backtracking" pattern guide. hellointerview.com/learn/code/patterns/recursion-backtracking. If you want interview-specific framing in plain English with problem sets, this is the most maintained free reference I know of.

The Takeaway

Backtracking is not three steps. It's one question with a three-step consequence. The question is "what's the menu at this level of recursion?" and the consequence — choose, recurse, un-choose — is mechanical once you've answered it.

If you leave this post with one thing, let it be the habit of asking the menu question out loud before you touch the keyboard. Say it to the interviewer, say it to yourself on the whiteboard, say it into the quiet of your kitchen at 11pm when you're grinding LeetCode alone. What's the menu at each level? Then the recursion writes itself and you never freeze up again.