Notes

Backtracking

13 min read

important mid · part of Skills & Topics · Senior SWE Roadmap · related: Dynamic Programming · Greedy Algorithms · Arrays & Strings · DFS

Why this matters / recognition signals

Backtracking is depth-first search over a tree of choices, where each branch is explored fully before being undone and the next branch tried. It’s how you enumerate — exhaustively but not wastefully — every valid combination, permutation, or arrangement that satisfies a set of constraints, when there’s no formula or greedy rule that shortcuts straight to the answer.

Recognition signals — reach for backtracking when the problem says:

  • “generate all subsets / permutations / combinations”
  • “find all valid ways to place/arrange X subject to constraints” (N-Queens, Sudoku)
  • “does a path/word exist in this grid/graph following adjacency rules” (Word Search)
  • The search space is a sequence of decisions, each decision narrows what’s still valid, and an invalid partial choice can be detected before completing it (this last part is what separates backtracking from plain brute-force enumeration — see pruning below)

Core mechanism: choose → explore → un-choose

Every backtracking solution follows the same four-part shape, visible directly in the subsets implementations below: a base/completion check (record the partial solution once it’s valid or complete), a loop over the choices available at this point, a validity/pruning check before committing to each choice, and — critically — undoing that choice after the recursive call returns, before the loop moves to the next sibling choice.

The “undo” step is what makes this backtracking rather than plain forward-only recursion — without it, sibling branches would see contamination from a previous branch’s choices, because most implementations mutate one shared partial-solution structure in place rather than copying it at each level (copying works too, but costs more and is why “add then remove” is the idiomatic form).

Recursion tree: subsets of [1, 2, 3]

Each node is a decision point (“include this element or not”); every root-to-node path is a valid subset in progress.

flowchart TD
    Root["[ ]"] -->|include 1| N1["[1]"]
    Root -->|skip 1| N2["[ ]"]
    N1 -->|include 2| N11["[1,2]"]
    N1 -->|skip 2| N12["[1]"]
    N2 -->|include 2| N21["[2]"]
    N2 -->|skip 2| N22["[ ]"]
    N11 -->|include 3| N111["[1,2,3]"]
    N11 -->|skip 3| N112["[1,2]"]
    N12 -->|include 3| N121["[1,3]"]
    N12 -->|skip 3| N122["[1]"]
    N21 -->|include 3| N211["[2,3]"]
    N21 -->|skip 3| N212["[2]"]
    N22 -->|include 3| N221["[3]"]
    N22 -->|skip 3| N222["[ ]"]

    style N111 fill:#5a3,color:#000
    style N112 fill:#5a3,color:#000
    style N121 fill:#5a3,color:#000
    style N122 fill:#5a3,color:#000
    style N211 fill:#5a3,color:#000
    style N212 fill:#5a3,color:#000
    style N221 fill:#5a3,color:#000
    style N222 fill:#5a3,color:#000

Every leaf (green) is a distinct subset — 2^3 = 8 of them, one per root-to-leaf path, since each of the 3 elements independently is “in or out.” This is pure enumeration with no pruning: the whole tree is visited because every leaf is a valid answer.

Pruning: what turns exponential enumeration into something practical

Pure enumeration visits every leaf of the full tree. Pruning cuts off a branch the moment a partial choice is provably invalid — before wasting time completing it. N-Queens is the clean example: placing queen k in a column that shares a row, column, or diagonal with any already-placed queen can never lead to a valid solution, so that whole subtree (every arrangement of queens k+1..n under that placement) is skipped without ever being visited.

flowchart TD
    Root["place queen 1
(4 columns to try)"] --> A["col 0"]
    Root --> B["col 1"]
    Root --> C["col 2"]
    Root --> D["col 3"]
    A --> A1["queen2: col0 same-col, invalid — PRUNED"]
    A --> A2["queen2: col1 diagonal, invalid — PRUNED"]
    A --> A3["queen2: col2 valid — recurse deeper"]
    A --> A4["queen2: col3 diagonal, invalid — PRUNED"]

    style A1 fill:#933,color:#fff
    style A2 fill:#933,color:#fff
    style A4 fill:#933,color:#fff
    style A3 fill:#5a3,color:#000

The constraint check (row/column/diagonal occupied?) is what makes N-Queens tractable at all for the classic interview sizes (n=4 to n=8) — without it, the search would explore n^n placements; with row-by-row placement alone it drops to n!; with full pruning of column and diagonal conflicts as you go, the vast majority of that n! is cut off before ever being generated.

Worked numeric trace: N-Queens, n = 4

State: queens[row] = column of the queen placed in that row. Try columns left to right at each row; skip (prune) any column that conflicts with an already-placed queen.

RowTry colConflict check vs placed queensValid?Action
00none placed yetyesplace queens[0]=0
10same column as row 0noprune
11diagonal with row 0 (col diff 1 = row diff 1)noprune
12col diff 2, row diff 1 — safeyesplace queens[1]=2
20diagonal with row1(col2)? diff2 vs diff1, no; vs row0(col0): diff0, row diff2 — same col!noprune
21vs row0(col0): diagonal (diff1=diff2? no, diff1,rowdiff2 safe); vs row1(col2): diagonal (diff1,rowdiff1) — conflictnoprune
22same column as row1noprune
23vs row0(col0): diff3,rowdiff2 safe; vs row1(col2): diff1,rowdiff1 — conflictnoprune
2—all 4 columns pruned at row 2—backtrack to row 1
13vs row0(col0): diff3, rowdiff1 — safeyesplace queens[1]=3
21vs row0(col0): diff1,rowdiff2 safe; vs row1(col3): diff2,rowdiff1 safeyesplace queens[2]=1
3…(continue similarly)yesqueens[3]=… completes a solution

The key moment is the “all 4 columns pruned at row 2” row: rather than continuing to place queens in rows 3 with an already-invalid row-2 placement (which pure enumeration would do, wasting an entire subtree), backtracking abandons row 2 immediately, undoes queens[1]=2, and retries row 1 with the next column. That single early abandonment is what pruning buys — the invalid subtree under queens[1]=2 is never explored past row 2.

Java — backtracking template (Subsets) and pruning example (N-Queens count)

import java.util.ArrayList;
import java.util.List;
 
public class BacktrackingExamples {
 
    // Pure enumeration: all subsets of nums.
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }
 
    private void backtrack(int[] nums, int start, List<Integer> partial, List<List<Integer>> result) {
        result.add(new ArrayList<>(partial));   // every partial state along the way is a valid subset
        for (int i = start; i < nums.length; i++) {
            partial.add(nums[i]);                        // choose
            backtrack(nums, i + 1, partial, result);      // explore
            partial.remove(partial.size() - 1);           // un-choose (backtrack)
        }
    }
 
    // Enumeration + pruning: count valid N-Queens placements.
    public int totalNQueens(int n) {
        int[] queens = new int[n];   // queens[row] = column
        return solve(queens, 0, n);
    }
 
    private int solve(int[] queens, int row, int n) {
        if (row == n) {
            return 1;   // completed a valid full placement
        }
        int count = 0;
        for (int col = 0; col < n; col++) {
            if (isSafe(queens, row, col)) {   // pruning check — skip invalid branches entirely
                queens[row] = col;                     // choose
                count += solve(queens, row + 1, n);    // explore
                // no explicit undo needed: queens[row] is overwritten on the next iteration
            }
        }
        return count;
    }
 
    private boolean isSafe(int[] queens, int row, int col) {
        for (int r = 0; r < row; r++) {
            int c = queens[r];
            if (c == col || Math.abs(c - col) == Math.abs(r - row)) {
                return false;   // same column, or same diagonal
            }
        }
        return true;
    }
}

Python — backtracking template (Subsets) and pruning example (N-Queens count)

def subsets(nums: list[int]) -> list[list[int]]:
    result: list[list[int]] = []
    partial: list[int] = []
 
    def backtrack(start: int) -> None:
        result.append(partial.copy())          # every partial state is a valid subset
        for i in range(start, len(nums)):
            partial.append(nums[i])             # choose
            backtrack(i + 1)                     # explore
            partial.pop()                        # un-choose (backtrack)
 
    backtrack(0)
    return result
 
 
def total_n_queens(n: int) -> int:
    queens = [-1] * n   # queens[row] = column
 
    def is_safe(row: int, col: int) -> bool:
        for r in range(row):
            c = queens[r]
            if c == col or abs(c - col) == abs(r - row):
                return False   # same column, or same diagonal
        return True
 
    def solve(row: int) -> int:
        if row == n:
            return 1            # completed a valid full placement
        count = 0
        for col in range(n):
            if is_safe(row, col):        # pruning check
                queens[row] = col        # choose
                count += solve(row + 1)  # explore
                # no explicit undo needed: queens[row] is overwritten next iteration
        return count
 
    return solve(0)

N-Queens prunes on a global constraint (no shared row/column/diagonal across all placed queens so far). Word Search prunes differently — on local adjacency and a visited set — which is worth seeing explicitly because it’s the more common shape of pruning in grid/graph backtracking problems: does the next cell match the next required character, and has this cell already been used earlier in the current path?

public class WordSearch {
 
    public boolean exist(char[][] board, String word) {
        int rows = board.length, cols = board[0].length;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (dfs(board, word, r, c, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
 
    private boolean dfs(char[][] board, String word, int r, int c, int idx) {
        if (idx == word.length()) {
            return true;   // matched every character
        }
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length
                || board[r][c] != word.charAt(idx)) {
            return false;  // out of bounds, or character mismatch — prune
        }
 
        char original = board[r][c];
        board[r][c] = '#';   // mark visited in place (choose)
 
        boolean found = dfs(board, word, r + 1, c, idx + 1)
                || dfs(board, word, r - 1, c, idx + 1)
                || dfs(board, word, r, c + 1, idx + 1)
                || dfs(board, word, r, c - 1, idx + 1);
 
        board[r][c] = original;   // un-mark before returning (backtrack)
        return found;
    }
}
def exist(board: list[list[str]], word: str) -> bool:
    rows, cols = len(board), len(board[0])
 
    def dfs(r: int, c: int, idx: int) -> bool:
        if idx == len(word):
            return True   # matched every character
        if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[idx]:
            return False  # out of bounds, or character mismatch — prune
 
        original = board[r][c]
        board[r][c] = "#"    # mark visited in place (choose)
 
        found = (
            dfs(r + 1, c, idx + 1)
            or dfs(r - 1, c, idx + 1)
            or dfs(r, c + 1, idx + 1)
            or dfs(r, c - 1, idx + 1)
        )
 
        board[r][c] = original   # un-mark before returning (backtrack)
        return found
 
    return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))

The '#' mark-and-restore is doing exactly the same job as queens[row] = col being overwritten and partial.pop() in the earlier examples — record a choice, recurse, then leave the shared structure exactly as the caller found it. The mismatch check (board[r][c] != word.charAt(idx)) is the pruning: a branch dies the instant a single character fails to match, rather than continuing to explore all four directions from a cell that can never complete the word.

Complexity comparison

ApproachTimeSpaceNotes
Pure enumeration, no pruning (Subsets)O(2^n · n)O(n) recursion depth + O(2^n · n) outputEvery subset must be generated and copied out — this is the theoretical minimum, not overhead to remove
Backtracking with pruning (N-Queens)O(n!) worst case, far less in practiceO(n) for the queens array + recursion depthPruning cuts subtrees before generating them — actual runtime is usually orders of magnitude below the n! bound
Backtracking with pruning (Word Search)O(rows·cols·4^L) where L = word lengthO(L) recursion depthBounded branching factor (4 directions) × early-exit on mismatch, not full grid enumeration
Brute force without early terminationSame asymptotic bound as backtracking, but no early exitSameThe asymptotic worst case is often identical to backtracking’s — pruning’s win is practical constant-factor and average-case, not a better Big-O in the adversarial worst case

Common pitfalls

  • Forgetting to un-choose (the “backtrack” step): mutating a shared list/array/board in place and forgetting to remove the last choice before the next sibling iteration leaves state contamination — sibling branches silently see choices from a previous branch that should have been undone. This is the single most common backtracking bug.
  • Copying the partial solution instead of mutating + undoing, without realizing the cost: result.add(new ArrayList<>(partial)) (copy at the leaf/record point) is fine and necessary — Java lists are mutable references, so storing partial itself instead of a copy means every stored “subset” ends up pointing to the same list, which later mutates out from under all of them.
  • Pruning too late: checking validity only once a complete candidate is built (generate-then-filter) throws away all of pruning’s benefit — the check has to happen before recursing deeper, not after the leaf is reached, otherwise the algorithm degrades to the pure-enumeration bound.
  • Off-by-one in the “start index” for combinations/subsets: using start instead of start + 1 in the recursive call (or vice versa) is the difference between generating combinations without repetition and permitting a element to be reused — a classic source of duplicate or missing results.
  • Not handling duplicate input values: Subsets II / Permutations II style problems (duplicate elements in the input) need an explicit “skip this branch if it’s the same value as the previous sibling at this level” check, or duplicate results get emitted despite the algorithm being otherwise correct.
  • Confusing “no solution found” with “all pruned”: in constraint problems (N-Queens, Sudoku), a false/empty-result outcome after full exploration is a legitimate valid answer for some inputs (e.g. N-Queens has no solution for n=2 or n=3) — don’t assume a bug just because backtracking returns nothing.

Practice problems

  • Subsets (pure enumeration template, worked above)
  • Permutations (pure enumeration, “used” tracking instead of a start index since order matters)
  • Combination Sum (enumeration + a numeric pruning bound — stop a branch once the running sum exceeds the target)
  • N-Queens / N-Queens II (enumeration + row/column/diagonal constraint pruning, worked above)
  • Word Search (enumeration + grid-adjacency pruning + visited-cell tracking with explicit un-mark on backtrack)
  • Sudoku Solver (enumeration + row/column/box constraint pruning — the natural “next level up” from N-Queens)
  • Palindrome Partitioning (enumeration + a validity pruning check per candidate substring)

Interview angles

  • “What’s the difference between backtracking and plain DFS?” — DFS explores a graph/tree that already exists; backtracking constructs a solution incrementally and explicitly undoes choices to reuse shared state across branches — the “un-choose” step is the defining feature DFS over a static graph doesn’t need.
  • “How would you speed this up?” — name pruning specifically: identify the earliest point in the decision sequence where a partial choice can be proven invalid, and move the validity check there instead of checking only at completed leaves.
  • “What’s the actual worst-case time complexity, and does pruning change it?” — be honest that pruning improves practical/average-case runtime enormously but the asymptotic worst case (e.g. N-Queens’ O(n!) bound) is often unchanged, since an adversarial input can still force near-full exploration.
  • “Backtracking vs DP — when would you use which here?” — backtracking enumerates all valid solutions (or existence); DP is for counting or optimizing over solutions without enumerating each one explicitly — if the problem only asks “how many” or “what’s the best,” and subproblems overlap, DP is usually the better fit even when a backtracking solution also exists (see Dynamic Programming).
  • “How do you avoid duplicate results when the input has duplicate values?” — sort the input first, then at each recursion level skip a candidate if it equals the previous sibling candidate that was already fully explored at that same level.
  • “Can this be done iteratively instead of recursively?” — yes, with an explicit stack holding the same state backtracking’s call stack would hold (partial solution + next choice index) — useful to mention if recursion depth is a concern (e.g. very large n), though it’s rarely asked for in practice over the recursive form.

My Notes

Graph View

Backlinks