Backtracking 101

What backtracking is

Try, recurse, undo

Backtracking builds a solution one choice at a time. At each step it tries every valid option, recurses to make the next choice, and then undoes the option before trying the next one. Picture it as a depth-first walk over a tree of decisions: each path from the root to a leaf is one complete candidate. Whenever a partial path can no longer lead to a valid answer, you stop exploring it; this is called pruning, and it is what makes backtracking practical.

Signals in a problem statement

• "Return all" subsets, permutations, combinations, partitions, or arrangements.
• "Place N queens", "solve the Sudoku", "fill the board".
• "Does the word exist in the grid?" following adjacent cells without reuse.
• "Generate all valid parentheses", "all phone-keypad letter combinations".
• Constraints are small: n ≤ 10 to 20. Exponential time is expected and acceptable.

If the question asks only for a count or the best value and the constraints are large, dynamic programming is often the better tool; backtracking enumerates every option.

The three decisions

Before writing code, answer three questions:

1. State: what describes a partial solution? (the current path, an index into the input, the remaining target)
2. Choices: what can be added next from this state?
3. Goal: when is the path complete and worth recording?

Then add pruning: which choices can be rejected immediately? For example, in combination sum, once the sorted candidates exceed the remaining target, every later candidate does too, so you can stop the loop.

Mental model

Think of exploring a maze with a ball of thread. You walk forward, and when you hit a dead end you wind the thread back to the last junction and take the next turn. The "undo" step is winding back the thread.

Core patterns with templates

The universal template

def backtrack(state, choices):
    if is_goal(state):
        record(state)
        return
    for c in choices(state):
        if valid(state, c):
            apply(state, c)
            backtrack(state, choices)
            undo(state, c)

1. Subsets (include or skip, by start index)

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

path[:] copies the list; appending path itself would record the same list object every time, which ends up empty.

2. Combination sum (reuse allowed, prune on sorted input)

def combination_sum(cands, target):
    cands.sort()
    out, path = [], []
    def go(start, remain):
        if remain == 0:
            out.append(path[:])
            return
        for i in range(start, len(cands)):
            if cands[i] > remain:
                break
            path.append(cands[i])
            go(i, remain - cands[i])
            path.pop()
    go(0, target)
    return out

Passing i (not i + 1) allows the same number again. Example: [2, 3, 6, 7], target 7 gives [2, 2, 3] and [7].

3. Grid search with temporary marking

def exist(board, word):
    rows, cols = len(board), len(board[0])
    def go(r, c, k):
        if k == len(word):
            return True
        if not (0 <= r < rows and 0 <= c < cols) or board[r][c] != word[k]:
            return False
        board[r][c] = "#"
        found = any(go(r + dr, c + dc, k + 1) for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)))
        board[r][c] = word[k]
        return found
    return any(go(r, c, 0) for r in range(rows) for c in range(cols))

4. N-Queens with constraint sets

Place one queen per row. Track used columns and both diagonals (r - c and r + c) in sets so each check is O(1).

def n_queens(n):
    cols, d1, d2, out, pos = set(), set(), set(), [], []
    def go(r):
        if r == n:
            out.append(["." * c + "Q" + "." * (n - c - 1) for c in pos])
            return
        for c in range(n):
            if c in cols or r - c in d1 or r + c in d2:
                continue
            cols.add(c); d1.add(r - c); d2.add(r + c); pos.append(c)
            go(r + 1)
            cols.remove(c); d1.remove(r - c); d2.remove(r + c); pos.pop()
    go(0)
    return out

Complexity, mistakes and edge cases

Complexity

The extra factor of n (or k) comes from copying each result. Space is O(depth) for the recursion and the path, plus the output.

Common mistakes

• Not copying the path when recording it (out.append(path) instead of path[:]).
• Forgetting to undo. Every append needs a matching pop; every board mark needs a restore. A missing undo corrupts later branches silently.
• Duplicate results when the input has repeated values. Sort first, then skip nums[i] if i > start and nums[i] == nums[i - 1].
• Wrong start index. i + 1 means each element at most once; i means reuse allowed; 0 with a used array means permutations.
• Checking the goal too late, after already going out of bounds, or recording a result before it is complete.
• No pruning. Without the early break in combination sum, the search explores many paths that can never succeed.
• Recursion depth. Usually fine because n is small, but a word of 10⁴ characters on a grid could exceed Python's limit.

Edge cases

Empty input (subsets returns [[]]), target 0, candidates larger than the target, n = 1, n = 2 and n = 3 for N-Queens (no solution for 2 and 3), a word longer than the number of cells, and single-cell boards.

Estimating whether it will finish

Before coding, estimate the size of the search tree. For n = 20 subsets, 2^20 is about a million: fine. For 12 permutations, 12! is about 479 million: too slow in Python without strong pruning. Saying this estimate aloud shows the interviewer you understand the cost.

Variations and practise

How interviewers twist it

• Permutations with duplicates. Sort, keep a used array, and skip a value if it equals the previous one and the previous one is not currently used.
• Each number used once, with duplicates in the input (combination sum II). Sort, recurse with i + 1, and skip equal neighbours at the same depth.
• Palindrome partitioning. The choice at each step is where to cut next; only recurse when the piece is a palindrome. Precompute a palindrome table to speed up the check.
• Generate valid parentheses. Track open and close counts; add ( while open < n, and ) while close < open.
• Sudoku solver. Pick the empty cell with the fewest options first; this pruning makes a huge difference.
• Count instead of list. If only the number of solutions is needed, return counts from the recursion; with overlapping states, add memoisation and it becomes dynamic programming.
• Word search for many words. Build a trie of the words and walk it alongside the grid so you search all words at once.

How to explain it

Describe the state, the choices and the goal before coding: "The state is the current row; the choices are the columns not attacked; the goal is reaching row n." Then name your pruning rule.

Practise

The problems below cover subsets, combinations with reuse, searching a word in a grid, and N-Queens. Use the same template for all of them and notice that only the state, the choices and the goal change.