Backtracking — the shape behind dozens of interview problems.

Backtracking in Python

def subsets(nums: list[int]) -> list[list[int]]:
    out: list[list[int]] = []
    def go(i: int, cur: list[int]) -> None:
        if i == len(nums):
            out.append(cur[:])
            return
        cur.append(nums[i])
        go(i + 1, cur)
        cur.pop()
        go(i + 1, cur)
    go(0, [])
    return out

See language-specific tabs at /languages/python/patterns and the SQL variant at /languages/sql/patterns.

Related patterns

Frequently asked questions

What is the backtracking pattern?

Backtracking is dfs through a decision tree with pruning and state restoration. Exponential in the decision depth; pruning is the whole game.

When should I use backtracking?

Use it when: Generate all subsets / permutations / combinations. Constraint-satisfaction (N-queens, sudoku). Paths in a grid with branching constraints.

What are the most common backtracking bugs?

Forgetting to pop/undo state before the sibling branch. Copying the whole state at each leaf (O(n²) memory blow-up). Missing pruning conditions — exponential becomes timeout.

What problems use the backtracking pattern?

Representative scenarios: Pizza Topping Combos — subsets of ingredients that meet a rule. Radar Placement — N-queens variant on a grid. Maze Inscription — word search on a letter grid.

Is backtracking on the Blind 75?

Yes — Backtracking is one of the core patterns behind the Blind 75 list. See /blind-75 for the complete mapping.