Backtracking

DFS through a decision tree, undoing choices on failure to try alternatives.

When to use

N-Queens, sudoku solver, word search, combination sum, palindrome partitioning.

Complexity

time Exponential — typically O(b^d) (e.g., O(n!) for permutations, O(2^n) for subsets)space O(d)

Backtracking explores a decision tree of branching factor b and depth d; pruning helps in practice but does not change the worst-case ceiling. Space is dominated by the recursion stack and the in-progress candidate.

How it works

Backtracking is DFS through a decision tree where you make a choice, recurse, then undo the choice before trying the next option. The undo step is what distinguishes it from naive DFS — by sharing one mutable state (the current path, the board, the used set) across all branches, you avoid the O(depth) copying cost at each call.

Pruning is the difference between an algorithm that finishes and one that times out. Constraint checks (this placement creates a conflict), bounding (the best possible from here is worse than the current best), and symmetry breaking (don't try equivalent permutations) can transform a 10^9 tree into a 10^4 traversal. N-queens, sudoku, and word search all rely on aggressive pruning.

Recognize backtracking by the problem statement: 'find all', 'count all', 'is there any' over a combinatorial space, often with constraints that aren't easily expressed as DP transitions. Time complexity is hard to state cleanly — usually O(branching^depth) in the worst case, but pruning makes practical performance much better than the worst-case bound.

Key insight

Sharing one mutable state and undoing changes on the way back up turns combinatorial enumeration from O(depth * outputs) memory into O(depth) — the same state structure serves every branch, with constraint-driven pruning collapsing most subtrees before they expand.

Common pitfalls

Forgetting to undo the choice after the recursive call, leaving stale state for the next branch.
Appending the live mutable path to results instead of a copy, so all results point to the same (eventually empty) list.
Not pruning aggressively enough — N-queens without diagonal checks is 8^8, with checks it's a few hundred nodes.
On grids, marking a cell visited but forgetting to unmark on the way back, blocking later branches from using it.
Confusing 'find one solution' (return early on first success) with 'find all' (collect and continue) — the recursion's return value differs.

Variations

Find all solutions: collect on success, continue exploring.
Find any one solution: return a boolean upward, short-circuit on first true.
Count solutions: return integer count, sum over children.
Constraint satisfaction (N-queens, sudoku): prune via per-row/col/diagonal sets.
Word search / path on grid: DFS with visited mark + unmark on backtrack.

Template

void backtrack(List<Integer> path, /* state */ int start) {
    if (/* goal reached */) {
        result.add(new ArrayList<>(path));
        return;
    }
    for (int i = start; i < n; i++) {
        if (/* prune */) continue;
        path.add(choices[i]);            // choose
        backtrack(path, i + 1);          // explore
        path.remove(path.size() - 1);    // un-choose
    }
}

Problems using this pattern

Easiest first · Blind 75 above NeetCode 150

Practice these problems

Solve mode — formulate the approach, then reveal. 4 problems.