Backtracking Template — Recognition, Choose/Undo Rhythm, Three Walkthroughs

Backtracking is depth-first search dressed up in an interview shirt. What makes it "backtracking" — as opposed to "recursion" — is the perfectly mirrored choose and undo that sandwich every recursive call. Get that rhythm right and subsets, permutations, and N-Queens all fall out of one template. Get it wrong and you'll spend a debugging session wondering why every entry in your result list looks identical.

Recognition — when to reach for it

Backtracking is the right tool when all four of these hold:

1. You're building the solution incrementally, one choice at a time.
2. The final answer is a combination, permutation, subset, arrangement, or path — not an aggregate like "count" or "max sum" (those want DP).
3. You need to enumerate all valid solutions, count them, or find one that satisfies constraints. (If you just want the best, and choices interact, you're probably in DP territory.)
4. The naïve enumeration is exponential — 2ⁿ, n!, nᵏ — but the tree has prunable branches: choices you can rule out early without fully exploring them.

That last point is what separates a backtracking solution from a brute-force one. If you can't prune, you're just doing DFS over the full 2ⁿ tree, which is fine when n = 20 but pointless as a "technique" — the interviewer wanted to see you recognise the prunes.

Mental model — DFS with explicit state

Every backtracking algorithm is a depth-first walk over a decision tree. Each internal node is a partial solution; each edge is a choice. Leaves are either complete solutions or dead ends.

The recursion carries state: usually a growing list (the choices made so far), sometimes plus auxiliary bookkeeping (which items have been used, which columns are attacked, running sum). Two rules make the state coherent across sibling branches:

1. Choose before you recurse. Mutate the state to reflect the choice you're about to explore.
2. Undo after you return. Revert the mutation before trying the next sibling choice.

Miss the second half and every sibling recursion inherits the mutations from its predecessors — quietly wrong output that looks right on small tests and explodes on medium ones.

The one other rule that catches every backtracking learner exactly once:

3. Snapshot the state when recording a solution. result.append(current[:]), not result.append(current). Appending current records a reference; every subsequent mutation shows up in the recorded solution. Your result fills with clones of the final state and every "solution" looks identical.

If you internalise those three rules, the "flavour" of the backtracking problem — subsets, permutations, N-Queens — is just a swap of what "choice" means.

The template

def backtrack(state):
    if is_complete(state):
        record(state)   # copy, not reference
        return

    for choice in candidate_choices(state):
        if not is_valid(state, choice):
            continue        # prune

        apply(state, choice)   # choose
        backtrack(state)       # recurse
        undo(state, choice)    # undo

The is_valid check before mutation is the prune. The apply and undo are the mirrored halves — same choice, opposite direction. Every backtracking problem below is one filling of the four slots (is_complete, candidate_choices, apply, undo).

Three flavours worth naming

• Choice-per-element (subsets, combinations). For each element, include it or skip it. The tree has 2ⁿ leaves at most.
• Choice-of-remaining (permutations, arrangements). At each step, pick from the elements you haven't used yet. The tree has n! leaves at most.
• Constrained placement (N-Queens, Sudoku, graph colouring). Choose a slot value from a large space, gated by a validity constraint that prunes most of the space per step.

Every backtracking problem you'll see in an interview is one of those three, sometimes with a wrinkle (dedup, ordering, sum target). Naming the flavour up front tells you what candidate_choices looks like.

Walkthrough 1 — LeetCode 78, Subsets

Given an integer array nums with distinct elements, return all possible subsets. The result cannot contain duplicate subsets. Return in any order.

Recognition. Enumerate all combinations ✓. 2ⁿ leaves is the naïve tree; there's no pruning needed because every partial subset is a valid subset — we record at every node, not just leaves.

Flavour. Choice-per-element. But we recast it as "choose a start index and iterate from there", which handles the include/skip decision without an explicit binary branch.

def subsets(nums: list[int]) -> list[list[int]]:
    result: list[list[int]] = []

    def backtrack(start: int, current: list[int]) -> None:
        result.append(current[:])   # every node is a valid subset
        for i in range(start, len(nums)):
            current.append(nums[i])       # choose
            backtrack(i + 1, current)     # recurse with next start
            current.pop()                 # undo

    backtrack(0, [])
    return result

The start parameter is the tiny detail that prevents duplicates: after including nums[i], subsequent choices must come from nums[i+1:]. Without start, we'd emit [1, 2] and [2, 1] as separate subsets — wrong for this problem.

Trace nums = [1, 2, 3].

• backtrack(0, []) records []. Loop i = 0, 1, 2.
  • i = 0: append 1. backtrack(1, [1]) records [1]. Loop i = 1, 2.
    • i = 1: append 2. backtrack(2, [1, 2]) records [1, 2]. Loop i = 2.
      • i = 2: append 3. backtrack(3, [1, 2, 3]) records [1, 2, 3]. Loop empty. Return.
      • Pop 3.
    • Pop 2.
    • i = 2: append 3. backtrack(3, [1, 3]) records [1, 3]. Return. Pop 3.
  • Pop 1.
  • i = 1: append 2. …records [2], [2, 3].
  • i = 2: append 3. …records [3].

Result: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]. Eight subsets, as expected for n = 3 (2³).

Notice the shape: for a bushy tree like this, the choose/undo rhythm is what keeps current clean across siblings. If we appended without popping, the second recursion at start = 0 would start from [1, 2, 3] and everything downstream would be corrupt.

Walkthrough 2 — LeetCode 46, Permutations

Given an array nums of distinct integers, return all possible permutations.

Recognition. Enumerate all arrangements ✓. n! leaves — no way to shrink that asymptotically, but the algorithm's constant factors are what interviewers grade.

Flavour. Choice-of-remaining. At each step, pick any element not yet used. Track "used" with a boolean array; testing membership with if x in current is O(n) and turns a clean solution into an O(n × n!) one for no reason.

def permute(nums: list[int]) -> list[list[int]]:
    result: list[list[int]] = []
    used = [False] * len(nums)

    def backtrack(current: list[int]) -> None:
        if len(current) == len(nums):
            result.append(current[:])
            return

        for i, num in enumerate(nums):
            if used[i]:
                continue                  # prune
            used[i] = True                # choose
            current.append(num)
            backtrack(current)            # recurse
            current.pop()                 # undo
            used[i] = False

    backtrack([])
    return result

Two mutations at each choose, two matching mutations at each undo. Every mirror. Miss one — say, forgetting used[i] = False — and the algorithm marks elements as permanently used across sibling branches, producing dramatically wrong output.

Trace nums = [1, 2, 3].

• [] → try 1 → [1] → try 2 → [1, 2] → try 3 → [1, 2, 3] record. Backtrack.
• [1, 2] → try 3 (used), no more. Pop.
• [1] → try 3 → [1, 3] → try 2 → [1, 3, 2] record. Backtrack.

Continue similarly. Result: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]. Six permutations for n = 3 (3!).

The recognition question worth pausing on: why do we snapshot on if len(current) == len(nums) and not at every node the way we did in LC 78? Because LC 78's problem said "every subset is a valid answer" — every node of the tree is a solution. LC 46's problem says "only full permutations" — only leaves are. The is_complete check is a problem-defined predicate, not a template detail.

Walkthrough 3 — LeetCode 51, N-Queens

Place n queens on an n × n chessboard so that no two attack each other (no shared row, column, or diagonal). Return all distinct solutions as boards.

Now the pruning earns its keep. n! grows fast (n = 8 is 40,320), but with attack constraints most branches die immediately — for n = 8, only 92 boards actually work.

Flavour. Constrained placement. Place one queen per row (that's the "one per row" prune for free — no need to consider two queens in the same row). At each row, the choice space is columns 0..n-1; the constraint is "no shared column, no shared diagonal".

Diagonals as sets. For a queen at (row, col):

• Anti-diagonal (going ↗): all (r, c) with r + c equal. Store attacked anti-diagonals in one set.
• Main diagonal (going ↘): all (r, c) with r - c equal. Store attacked main-diagonals in another set.

Two set lookups per placement, O(1). This is what makes N-Queens tractable up to n ≈ 14 or so on a laptop.

def solveNQueens(n: int) -> list[list[str]]:
    result: list[list[str]] = []
    cols: set[int] = set()
    anti: set[int] = set()   # row + col
    main: set[int] = set()   # row - col
    queens: list[int] = []   # queens[r] = column of queen in row r

    def backtrack(row: int) -> None:
        if row == n:
            board = [
                "." * queens[r] + "Q" + "." * (n - queens[r] - 1)
                for r in range(n)
            ]
            result.append(board)
            return

        for col in range(n):
            if col in cols or (row + col) in anti or (row - col) in main:
                continue                  # prune

            cols.add(col)                 # choose
            anti.add(row + col)
            main.add(row - col)
            queens.append(col)

            backtrack(row + 1)            # recurse

            queens.pop()                  # undo
            cols.remove(col)
            anti.remove(row + col)
            main.remove(row - col)

    backtrack(0)
    return result

Four mutations at choose, four at undo. Same rhythm as LC 46, just more of them because the constraint bookkeeping is richer. Every backtracking problem you'll face in an interview is somewhere on this spectrum — the number of tracked pieces of state grows with the constraint's richness, but the choose/undo shape doesn't change.

For n = 4, the algorithm returns:

[
  [".Q..",
   "...Q",
   "Q...",
   "..Q."],

  ["..Q.",
   "Q...",
   "...Q",
   ".Q.."]
]

Two solutions, as expected. The prune deletes roughly 24 − 2 = 22 of the 24 possible column-permutation leaves before ever reaching row 4 in most branches — the win over unpruned brute force is stark.

Common bugs

The choose/undo rhythm deletes most bugs, but three survive that survival:

• Recording a reference instead of a copy. result.append(current) shares the same list object with every recorded "solution". Every solution in result then reflects current's final state after all recursion completes — usually the empty list. result.append(current[:]) (or list(current), or copy.copy(current)) snapshots.
• Asymmetric choose/undo. Two mutations at choose, one at undo. Or the undo happens before recursion. The state leaks across siblings. Manually verify every backtracking function has the same number of mutating statements above and below the recursive call.
• Pruning too late. Placing the check inside the recursive call ("recurse, then check validity at the top") wastes an entire subtree of work. The prune belongs before the mutation, at the if not is_valid guard.

When backtracking is not the tool

• You want the optimal answer, not all answers, and choices interact. DP or greedy. Backtracking will find the optimum by enumerating everything, but you're paying exponential time for a polynomial-time answer.
• The tree has no prunes. If every branch is valid, you're just doing brute-force enumeration — fine for tiny n, but stop pretending it's a technique. Reach for iterative bit-manipulation for subsets (for mask in range(1 << n)) which is a factor faster in practice.
• The state is too big to snapshot cheaply. If each solution is a 1000-element list, result.append(current[:]) is a costly O(k) copy at every leaf. Consider recording just the choices (indices) and rebuilding the full state on demand.
• Overlapping subproblems. Same partial state reached by different paths and re-explored each time. Memoise (which turns backtracking into top-down DP) or switch to bottom-up DP.

How the Algotrek tutor would prompt you here

When a learner opens a backtracking problem on Algotrek, the tutor doesn't reveal the template. It asks three questions, and only advances when each is answered in one sentence:

1. "What's the choice at each step?" — Forces the flavour to be named. "Include or skip the current element." "Pick any unused element." "Which column for this row's queen." Naming this is what tells you what candidate_choices looks like.
2. "Is every node a valid solution, or only the leaves?" — Determines where the record(state) call lives. LC 78 records at every node; LC 46 and LC 51 record only when the state is complete. Getting this wrong means either missing solutions or emitting garbage.
3. "What constraint lets you prune before recursing?" — This is where backtracking earns its keep. "Column already used." "Sum has exceeded target." "Element already in current." If you can't name a prune, you haven't found the technique yet — you've found brute force in a costume.

Answer all three and the template is a fifteen-minute typing exercise. Try the Subsets lesson on Algotrek to see the prompt-then-reveal flow on the friendliest backtracking problem, then step up to the Permutations lesson once the choose/undo rhythm is in your fingers.

Where to go next

• LC 77, Combinations. LC 78's little sibling with a size constraint. A natural graduation from "all subsets" to "subsets of size k".
• LC 39, Combination Sum. Elements can be reused; prune early when the running sum exceeds the target. Introduces sum-based pruning, which shows up in a dozen interview problems.
• LC 40, Combination Sum II. LC 39 plus dedup — sort first, then skip nums[i] == nums[i-1] at sibling level. The dedup pattern generalises to LC 47 (Permutations II) and LC 90 (Subsets II).
• LC 79, Word Search. 2D grid backtracking with visited-cell bookkeeping. Same choose/undo rhythm, applied to (row, col) moves instead of "next element".
• LC 37, Sudoku Solver. Constrained placement, boss level. Every row, column, and 3×3 box gets its own used set. A satisfying reward for owning N-Queens.

Cross-reference the sliding-window, two-pointer, binary-search, and monotonic-stack posts. Those four techniques prune by proving certain candidates never matter; backtracking prunes by proving certain branches never matter. Same meta-skill — what work can I prove I don't need to do? — solved with a decision tree instead of an invariant. Recognising which shape the problem hands you is the interview reflex the whole series is aimed at.

For the O(n · 2ⁿ) and O(n · n!) claims this pattern's naïve bounds cash in on, the Big-O cheat sheet's common-interview-algorithms table is the reference — subsets, permutations, and N-Queens all appear as rows there.