The Backtracking Pattern for Coding Interviews

The backtracking pattern is how you systematically explore every possible configuration of a problem — building a candidate one decision at a time, and abandoning any partial candidate the moment it can no longer lead to a valid answer. It is the engine behind generating all subsets, permutations and combinations, and behind constraint puzzles like N-Queens and Sudoku.

What backtracking is

Backtracking is a refined depth-first search over an implicit decision tree. Each node is a partial solution; each edge is a choice. You walk down a branch making choices, and when you hit a complete solution you record it. When a branch can't possibly succeed, you stop and walk back up — undoing your last choice — to try a different one.

The whole pattern fits in three words: choose → explore → un-choose. You make a choice, recurse to explore everything that follows from it, then undo the choice so the shared state is clean for the next option. That symmetric undo is what lets a single mutable path visit every branch without copying the world at each step.

The signal that a problem is backtracking

• The prompt says “generate all” or “find every” — all subsets, all permutations, all combinations, all valid arrangements.
• It is a constraint-satisfaction problem: place items so that rules hold (N-Queens, Sudoku, graph coloring, word/grid search).
• The answer is built incrementally and a partial answer can be rejected early before it is complete.
• The input is small — exponential blow-up is acceptable because n is tiny (often n ≤ 20).

If instead the problem asks for a single optimal value over overlapping subproblems, that is usually dynamic programming, not backtracking.

A reusable template

Nearly every backtracking solution is a specialization of this one shape. Keep it in your head and adapt the three marked lines:

def backtrack(path, choices):
    if is_solution(path):          # base case: complete candidate
        results.append(path[:])    # record a COPY, not the reference
        return
    for choice in choices:
        if not is_valid(path, choice):
            continue               # prune: skip choices that break a rule
        path.append(choice)        # 1. choose
        backtrack(path, next_choices(choices, choice))  # 2. explore
        path.pop()                 # 3. un-choose (undo the choice)

Three pieces do all the work. is_solution decides when a path is complete and worth recording. The is_valid guard is your pruning hook — the earlier you reject, the smaller the tree. And the append/pop pair must stay perfectly balanced so state is restored on the way back up. Recording path[:] (a copy) rather than path is essential, since the same list keeps mutating.

Worked examples

Subsets

Problem: Return every subset of a list of distinct numbers (the power set).

Key idea: at each index, choose to include or skip that element. Every node of the tree is itself a valid subset, so record the path at every call.

def subsets(nums):
    res = []
    def backtrack(start, path):
        res.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return res

Time O(n · 2ⁿ) — 2ⁿ subsets, each up to length n to copy. Space O(n) for the recursion depth plus the output.

Permutations

Problem: Return all orderings of a list of distinct numbers.

Key idea: a permutation uses every element exactly once, so track which indices are already used. The base case fires when the path length equals n.

def permute(nums):
    res, used = [], [False] * len(nums)
    def backtrack(path):
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack(path)
            path.pop()
            used[i] = False
    backtrack([])
    return res

Time O(n · n!) and space O(n). Note the used flag is also un-chosen — every piece of mutated state must be reset, not just the path.

Combination Sum

Problem: Find all combinations of candidates (reused freely) that sum to a target.

Key idea: pass start so combinations stay non-decreasing (no permuted duplicates), and let a number be reused by recursing with the same index. Prune as soon as the remaining target goes negative.

def combinationSum(candidates, target):
    res = []
    def backtrack(start, path, remaining):
        if remaining == 0:
            res.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                continue           # prune: this and (if sorted) later ones overshoot
            path.append(candidates[i])
            backtrack(i, path, remaining - candidates[i])  # i, not i+1: reuse allowed
            path.pop()
    candidates.sort()
    backtrack(0, [], target)
    return res

Sorting first lets you replace continue with break for an even tighter prune. Complexity depends on the target and candidate set, but the pruning is what keeps it tractable.

N-Queens

Problem: Place N queens on an N×N board so none attack each other.

Key idea: place one queen per row, top to bottom. Track attacked columns and both diagonals in sets so each placement check is O(1). A square is safe when its column, its row-col diagonal, and its row+col anti-diagonal are all free.

def solveNQueens(n):
    res, cols, diag, anti = [], set(), set(), set()
    board = [["."] * n for _ in range(n)]
    def backtrack(row):
        if row == n:
            res.append(["".join(r) for r in board])
            return
        for col in range(n):
            if col in cols or (row - col) in diag or (row + col) in anti:
                continue           # prune attacked squares
            cols.add(col); diag.add(row - col); anti.add(row + col)
            board[row][col] = "Q"
            backtrack(row + 1)
            board[row][col] = "."
            cols.discard(col); diag.discard(row - col); anti.discard(row + col)
    backtrack(0)
    return res

The constant-time conflict check via sets is the difference between a fast solution and one that re-scans the board each step.

Word Search

Problem: Decide whether a word can be formed by adjacent cells in a grid, without reusing a cell.

Key idea: start a DFS from each cell, matching one character per step. Mark the current cell visited before recursing into its four neighbors, then restore it on the way back — the classic un-choose.

def exist(board, word):
    rows, cols = len(board), len(board[0])
    def backtrack(r, c, i):
        if i == len(word):
            return True
        if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[i]:
            return False
        board[r][c] = "#"          # mark visited
        found = (backtrack(r+1, c, i+1) or backtrack(r-1, c, i+1) or
                 backtrack(r, c+1, i+1) or backtrack(r, c-1, i+1))
        board[r][c] = word[i]      # restore (un-choose)
        return found
    return any(backtrack(r, c, 0) for r in range(rows) for c in range(cols))

Worst case O(rows · cols · 4⁰) where L is the word length; the early character mismatch prunes most branches immediately.

Sudoku Solver

Problem: Fill a 9×9 board so every row, column, and 3×3 box contains 1–9.

Key idea: find the next empty cell, try digits 1–9, recurse, and return True the instant the board is full. Validate each digit against its row, column, and box before placing — the constraint check is the prune.

def solveSudoku(board):
    def valid(r, c, ch):
        for i in range(9):
            if board[r][i] == ch or board[i][c] == ch:
                return False
            if board[3*(r//3) + i//3][3*(c//3) + i%3] == ch:
                return False
        return True
    def backtrack():
        for r in range(9):
            for c in range(9):
                if board[r][c] == ".":
                    for ch in "123456789":
                        if valid(r, c, ch):
                            board[r][c] = ch
                            if backtrack():
                                return True
                            board[r][c] = "."   # un-choose
                    return False                # no digit fit; dead end
        return True                             # no empty cell left
    backtrack()

Returning early on the first solved board (rather than exploring further) is what makes the solver responsive on real puzzles.

Pruning tips & common mistakes

• Prune before you recurse. Check the constraint at the top of the loop — skipping an overshooting candidate or an attacked square avoids whole subtrees. Sorting the input often turns a continue into a break.
• Skip duplicate choices. When the input has repeats, sort it and skip a value equal to its predecessor at the same tree level (if i > start and nums[i] == nums[i-1]: continue) to avoid duplicate results.
• Pitfall — forgetting to un-choose. Every mutation (path, used flags, the board) must be reverted symmetrically, or later branches inherit stale state.
• Pitfall — storing a reference. Append path[:], not path; otherwise every saved result points at the same list that keeps changing.

FAQ

When should I use backtracking?

Use backtracking when a problem asks you to generate or count all valid configurations — all subsets, permutations, or combinations — or when it is a constraint-satisfaction problem like N-Queens or Sudoku where you build a solution incrementally and abandon partial candidates that violate the rules.

What is the backtracking mental model?

Choose, explore, un-choose. At each step you make a choice, recurse to explore the consequences of that choice, then undo the choice before trying the next one. The undo step is what lets a single mutable state object visit every branch of the decision tree.

What is the difference between backtracking and DFS?

Backtracking is depth-first search over an implicit decision tree where you also undo state on the way back up and prune branches that cannot lead to a valid solution. Plain DFS explores a fixed graph; backtracking explores choices and abandons dead ends early. For graph-flavored DFS and BFS, see graph algorithms for coding interviews.

How do you prune in backtracking?

Check constraints before recursing so you never descend into a branch that cannot succeed — for example, skip a queen placement that is already attacked, stop a combination sum once the remaining target goes negative, or sort and skip duplicate choices to avoid repeated results.

What is the most common backtracking mistake?

Forgetting to undo the choice after the recursive call, or appending a reference to the shared path instead of a copy. Always un-choose symmetrically and append path[:] (a copy) when recording a result.