Backtracking Explained: The Template That Solves Most Problems

Quick Answer

Backtracking builds a solution incrementally and abandons a partial candidate as soon as it cannot possibly work, then undoes the last choice and tries another. Every backtracking solution follows the same shape: choose an option, recurse to explore it, then undo the choice. It applies to subsets, permutations, combinations, N-queens, sudoku and word search. The undo step is what makes it backtracking rather than plain recursion.

The Idea: Brute Force That Gives Up Early

Some problems require exploring many combinations — every subset of a set, every arrangement of items, every way to place queens on a board. The number of possibilities is exponential, so generating all of them and filtering is hopeless for anything but tiny inputs.

Backtracking builds candidates one choice at a time and abandons a path the moment it becomes impossible. Placing two queens that attack each other means every arrangement extending that placement is invalid, so you stop immediately rather than filling the remaining board.

The mental picture is a maze. Walk down a corridor; if it dead-ends, walk back to the last junction and take a different turn. You never re-walk a branch you have already ruled out.

The template is always the same three steps:

def backtrack(state):
    if is_complete(state):
        record(state)
        return

    for option in available_options(state):
        if not is_valid(option, state):
            continue           # prune — do not even explore

        make_choice(option, state)      # 1. choose
        backtrack(state)                # 2. explore
        undo_choice(option, state)      # 3. undo   ← this is the backtracking

That undo step is the whole distinction. Recursion without it explores a tree; recursion with it explores a tree while reusing one mutable state, which is what makes it memory-efficient.

Pattern 1: Subsets and Combinations

At each element you make a binary choice — include it or not.

def subsets(nums):
    out, current = [], []

    def backtrack(start):
        out.append(current[:])         # every state is a valid subset
        for i in range(start, len(nums)):
            current.append(nums[i])    # choose
            backtrack(i + 1)           # explore, never reusing earlier items
            current.pop()              # undo

    backtrack(0)
    return out

Two details matter. current[:] copies the list — appending current itself would store a reference that later gets mutated, so every entry in the output would end up identical. This is the single most common bug in backtracking code.

And start prevents duplicates. Passing i + 1 means each element can only be chosen after the previous ones, so you get [1,2] but never [2,1] — correct for subsets, where order does not matter.

Combinations of size k are the same code with a size check instead of recording every state. Combination sum, where numbers can repeat, passes i instead of i + 1 so the same element can be reused.

For inputs with duplicate values, sort first and skip repeats at the same level:

if i > start and nums[i] == nums[i - 1]:
    continue        # skip duplicates at this depth

Pattern 2: Permutations

Here order matters, so every element is available at every position — you only need to avoid reusing one already placed.

def permutations(nums):
    out, current = [], []
    used = [False] * len(nums)

    def backtrack():
        if len(current) == len(nums):
            out.append(current[:])
            return

        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True; current.append(nums[i])   # choose
            backtrack()                               # explore
            current.pop(); used[i] = False            # undo BOTH

    backtrack()
    return out

Note that both pieces of state are undone. Forgetting to reset used[i] is the classic error and produces mysteriously missing results, because elements stay permanently marked as consumed.

The difference from subsets in one line: subsets iterate from start to avoid revisiting earlier elements; permutations iterate from 0 and use a used array. That distinction — whether order matters — decides which shape you reach for.

Complexity is O(n! × n): there are n! permutations and copying each costs O(n). For subsets it is O(2ⁿ × n). These are exponential by nature, which is why constraints on such problems are always small — typically n ≤ 20.

Pattern 3: Grids — N-Queens and Sudoku

Grid problems add a validity check before exploring, and that check is where the speed comes from.

def solve_n_queens(n):
    board = [-1] * n            # board[row] = column of the queen
    out = []

    def is_safe(row, col):
        for r in range(row):
            c = board[r]
            if c == col or abs(c - col) == abs(r - row):   # same column or diagonal
                return False
        return True

    def backtrack(row):
        if row == n:
            out.append(board[:]); return
        for col in range(n):
            if not is_safe(row, col):
                continue        # prune — skip this branch entirely
            board[row] = col    # choose
            backtrack(row + 1)  # explore
            board[row] = -1     # undo

    backtrack(0)
    return out

Placing one queen per row automatically removes row conflicts, so only columns and diagonals need checking. That reduction is a design choice, not something the algorithm gives you.

Pruning is what makes this feasible. Without is_safe, an 8-queens search would examine 8⁸ ≈ 16 million placements. With it, most branches die within a few rows. The same principle applies to sudoku: check the row, column and 3×3 box before recursing, and the search collapses from astronomically large to instant.

For word search in a grid, the state is the visited cells — mark a cell before exploring its neighbours, and unmark it afterwards so other paths can use it.

Getting It Right

Five things account for most backtracking bugs and most of the difference between a slow and a fast solution.

1. Copy when you record. out.append(current[:]), not out.append(current). Otherwise every stored result points at the same list, which is empty by the end.

2. Undo everything you changed. If you set two variables, reset both. Asymmetry between the choose and undo steps is the most common source of wrong output.

3. Prune as early as possible. Check validity before recursing, not after. Rejecting a branch at depth 2 skips everything below it; rejecting at depth 8 has already done the work.

4. Sort first when duplicates exist. It makes skipping repeats a simple adjacent comparison.

5. Know the complexity. Subsets O(2ⁿ), permutations O(n!), N-queens roughly O(n!) with heavy pruning. State these when asked, and note that pruning improves the practical time enormously without changing the worst case.

Practice order: subsets, then combinations, then permutations, then combination sum, then word search, then N-queens, then sudoku. Each adds one idea — a start index, a used array, a validity check, a grid — and by the last two the template feels routine rather than novel.

Frequently Asked Questions