Backtracking Interview Problems: 8 Patterns That Get Offers

Backtracking owns the hardest 15 minutes of coding interviews. N-Queens, Sudoku, Word Search, permutations — you've seen them on every 'top problems' list, and you still can't be sure you'd solve one live. Don't memorize four solutions. You'll drown. Learn one template and four constraint checks instead.

Here's the uncomfortable truth: every backtracking problem is the same three lines — choose, explore, unchoose — wrapped around a different validity test. Candidates who memorize boards fail the moment the interviewer tweaks the rules. Candidates who own the template adapt in seconds. Speed matters.

This guide gives you that template, then instantiates it four ways with runnable sketches: N-Queens with diagonal sets, Sudoku with box constraints, Word Search with visited restore, and the permutations/subsets/combination family. You'll also get pruning math that answers 'will this pass?' and an execution playbook for the whiteboard.

The One Template — Choose, Explore, Unchoose

All four problems compile to this skeleton. The base case records a snapshot. The loop enumerates candidates, prunes invalid ones BEFORE recursing, then does the three-beat: mutate, recurse, restore. Bugs live in exactly three places: missing snapshot (aliasing), missing restore (dirty state), prune-after-recurse (exponential blowup).

The problem-specific slots: candidates() is 'columns in this row' (Queens), 'digits 1-9' (Sudoku), '4 neighbors' (Word Search), 'unused elements from index i' (subsets). valid() is diagonal sets, box sets, visited+letter match, take/skip rules. Fill two slots, get a solution.

Practice drill: write the skeleton from memory 5 times, then fill Queens constraints without looking. That drill alone converts most 'I freeze' candidates into passers.

def backtrack(path, choices):
    if goal_reached(path):          # base case: record a snapshot
        results.append(list(path))
        return
    for c in candidates(choices):   # choice rule differs per problem
        if not valid(path, c):      # constraint check differs per problem
            continue                # prune: never recurse into dead branches
        path.append(c)              # CHOOSE
        backtrack(path, updated(choices, c))
        path.pop()                  # UNCHOOSE (restore!)

# Grid flavor: mark cell -> recurse 4 neighbors -> unmark cell.
# Set flavor:  add to used  -> recurse next index -> remove from used.

N-Queens — Diagonal Sets Do the Pruning

Place one queen per row; the choice is the column. Constraints: no shared column, no shared ↙↗ diagonal (r−c equal), no shared ↖↘ diagonal (r+c equal). Three sets enforce all of it in O(1) per candidate.

Pruning power: row 0 tries n columns, but row 1 tries only n−2 or fewer — attacked columns and diagonals vanish before recursion. n=8 yields 92 solutions in milliseconds; the raw n^n fantasy (16M placements) never materializes because most branches die at depth 2.

Interview narration: 'one queen per row, three sets, snapshot the board at depth n.' That's a 60-second explanation that scores full marks on structure before you write a line.

def solve_n_queens(n):
    res, cols, d1, d2, queens = [], set(), set(), set(), []
    def bt(r):
        if r == n:
            res.append(['.' * c + 'Q' + '.' * (n - 1 - c) for c in queens])
            return
        for c in range(n):
            if c in cols or (r - c) in d1 or (r + c) in d2:
                continue  # prune attacked squares before recursing
            cols.add(c); d1.add(r - c); d2.add(r + c); queens.append(c)
            bt(r + 1)
            queens.pop(); cols.discard(c); d1.discard(r - c); d2.discard(r + c)
    bt(0)
    return res  # n=4 -> 2 solutions; n=8 -> 92

Sudoku Solver — Box Sets Plus MRV Ordering

State: 9×9 board plus row/col/box digit sets. Choice: digit for the emptiest-constrained cell. Prune: digits already present in any of the three units never recurse. MRV ordering (minimum remaining values) picks the most constrained cell first, so contradictions surface at shallow depth.

Why MRV wins: a cell with 1 candidate forces the move; a cell with 7 candidates guesses. Row-major order guesses early and backtracks late — exponential waste. MRV on hard puzzles cuts solve time from seconds to milliseconds.

Box index arithmetic (r//3)*3 + c//3 maps 81 cells to 9 boxes. Get it wrong and valid boards reject — test box mapping on corners (0,0)→0, (0,8)→2, (8,0)→6, (8,8)→8 before running the solver.

def solve_sudoku(board):
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    empties = []
    for r in range(9):
        for c in range(9):
            v = board[r][c]
            if v == '.':
                empties.append((r, c))
            else:
                rows[r].add(v); cols[c].add(v)
                boxes[(r // 3) * 3 + c // 3].add(v)
    def candidates(r, c):
        used = rows[r] | cols[c] | boxes[(r // 3) * 3 + c // 3]
        return [d for d in '123456789' if d not in used]
    def bt(k):
        if k == len(empties):
            return True
        # MRV: pick emptiest-constrained cell among remaining
        nxt = min(range(k, len(empties)),
                  key=lambda i: len(candidates(*empties[i])))
        empties[k], empties[nxt] = empties[nxt], empties[k]
        r, c = empties[k]
        for d in candidates(r, c):
            board[r][c] = d
            rows[r].add(d); cols[c].add(d)
            boxes[(r // 3) * 3 + c // 3].add(d)
            if bt(k + 1):
                return True
            board[r][c] = '.'
            rows[r].discard(d); cols[c].discard(d)
            boxes[(r // 3) * 3 + c // 3].discard(d)
        return False
    bt(0)
    return board

Word Search — In-Place Visited With Restore

State: grid position plus matched-prefix length. Choice: 4 neighbors. Constraints: in-bounds, letter match, not visited (the '#' sentinel). Mark in place — no visited matrix copies — and restore on exit so sibling paths see a clean board.

Pruning that interviewers love: start DFS only from cells matching word[0]; rarer first letters prune harder. Early exits on length (word longer than cells) and letter-frequency counts (board lacks enough 'Z's) kill impossible cases in O(R×C) before any DFS.

Complexity honesty: worst case O(R×C×3^L) (4 first moves, ~3 thereafter excluding backtrack), but letter-match pruning collapses real boards. Say both numbers — the bound and why practice beats it.

def exist(board, word):
    R, C = len(board), len(board[0])
    def dfs(r, c, i):
        if i == len(word):
            return True
        if not (0 <= r < R and 0 <= c < C) or board[r][c] != word[i]:
            return False
        tmp = board[r][c]
        board[r][c] = '#'  # mark visited in place (no copied matrix)
        found = (dfs(r + 1, c, i + 1) or dfs(r - 1, c, i + 1)
                 or dfs(r, c + 1, i + 1) or dfs(r, c - 1, i + 1))
        board[r][c] = tmp  # UNCHOOSE: restore for sibling paths
        return found
    for r in range(R):
        for c in range(C):
            if board[r][c] == word[0] and dfs(r, c, 0):
                return True
    return False

Permutations, Subsets, Combination Sum — One Family

Permutations choose an ordering (used-array, any unused element); subsets choose membership (start-index, take-or-skip from i); Combination Sum adds a target with sorted early-stop (stop when remainder < 0) and same-index reuse for unlimited picks.

Duplicate handling is one rule: sort, then skip nums[i] when its twin nums[i−1] sits unused at the same level. That single line fixes Permutations II, Subsets II, and Combination Sum II identically.

Narrate the family mapping in interviews: 'permutations vary order, subsets vary membership, combinations add a sum target — same skeleton, different candidate rule.' Interviewers promote candidates who see families.

def permute_unique(nums):
    nums.sort()
    res, used, path = [], [False] * len(nums), []
    def bt():
        if len(path) == len(nums):
            res.append(list(path))
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue  # skip same-level twins (duplicate prune)
            used[i] = True
            path.append(nums[i])
            bt()
            path.pop()
            used[i] = False
    bt()
    return res

def subsets(nums):
    res, path = [], []
    def bt(i):
        res.append(list(path))  # every node is a valid subset
        for j in range(i, len(nums)):
            path.append(nums[j])
            bt(j + 1)  # start-index: never revisit earlier elements
            path.pop()
    bt(0)
    return res  # 2^n subsets

Pruning and Complexity — Answering Will This Pass

Raw bounds terrify: N-Queens O(n^n) placements, Sudoku O(9^81), Word Search O(4^L), permutations O(n!). Pruned reality: Queens places 92 solutions for n=8 in milliseconds, MRV Sudoku solves hard boards in milliseconds, Trie-guided Word Search II handles thousands of words on 12×12 boards.

The interview move is naming the effective branching: 'each queen kills a column and two diagonals, so depth-k branching is roughly n−2k'; 'MRV keeps Sudoku at 1–3 candidates per cell'; 'Trie guidance leaves ~1 live neighbor per Word Search step.' Numbers beat adjectives.

Time-box rule: if your search hasn't collapsed by depth 2, stop coding and add a constraint. No amount of micro-tuning saves unpruned exponential search — structure first, speed second.

# Pruning checklist — apply before claiming a solution passes:
# 1. N-Queens:   cols/diag sets      -> branching n -> ~n-2k at depth k
# 2. Sudoku:     row/col/box + MRV    -> 9 -> 1-3 typical candidates
# 3. Word Search: letter match + Trie -> 4 -> ~1 live neighbor
# 4. Combination: sorted + early stop -> unbounded -> bounded by target
# Time-box rule: if depth-2 branching isn't visibly collapsing, add a
# constraint BEFORE optimizing code. Structure beats micro-tuning.

Interview Execution Playbook — How to Present It Live

Minute 0–2: write the skeleton and label the two slots (candidates, valid). Interviewers score this instantly — it proves you've solved the class, not just an instance. Minutes 2–7: fill the slots with the constraint sets, narrating each ('columns, two diagonals').

Minutes 7–10: state complexity with pruning and run the smallest discriminating test (n=4 Queens → 2; 2×2 grid; [1,1,2] → 3 perms). Small tests catch diagonal arithmetic, aliasing, and skip-rule bugs in seconds.

Remaining time: invite follow-ups ('want duplicates handled? Trie-guided multi-word?'). Candidates who finish the core in 10 minutes and spend 20 on variants get hired; candidates who perfect one board for 40 minutes don't.

# Whiteboard execution order (say each step out loud):
# 1. Write skeleton: base case + loop + choose/recurse/unchoose (2 min)
# 2. Fill candidates() + valid() for THIS problem (5 min)
# 3. State complexity WITH pruning + name the pruning (1 min)
# 4. Self-test: n=4 queens / tiny grid / [1,1,2] perms (3 min)
# 5. Follow-ups: duplicates? bigger board? Trie guidance? (remaining)
# Red flags to voice early: copying state per call, appending live refs,
# pruning after recursion, hardcoded cell order in Sudoku.