← All patterns

Backtracking

Recursive search with pruning. Build candidate solutions incrementally and abort branches that violate constraints early. Bitmasks compress constraint state when feasible.

20 problems 4 Easy 9 Medium 7 Hard

Recursive depth-first search through a decision tree, pruning branches that can't yield valid solutions. The candidate state is built incrementally; failures cause backtracking via undoing the last change. Bitmasks compress constraint state (rows, cols, diagonals in N-Queens; row/col/box in Sudoku) into O(1) lookup.

The key to keeping backtracking tractable is aggressive pruning — abort branches the moment the partial state cannot possibly extend to a goal.

When to reach for this pattern

  • Enumerate all valid configurations under constraints
  • Combinatorial search where partial-state validity can be checked early
  • N-Queens, Sudoku, word search, expression generation
  • Constraint satisfaction with a small state space

Canonical template 

bool dfs(State& s) {
    if (isGoal(s)) { emit(s); return true; }
    for (auto& move : legalMoves(s)) {
        apply(s, move);
        if (dfs(s)) return true;       // or accumulate without early return
        undo(s, move);
    }
    return false;
}

// bitmask-pruned N-Queens
void dfs(int row, int cols, int diag, int anti) {
    if (row == n) { ++count; return; }
    int avail = ~(cols | diag | anti) & ((1 << n) - 1);
    while (avail) {
        int bit = avail & -avail;
        avail ^= bit;
        dfs(row + 1, cols | bit, (diag | bit) << 1, (anti | bit) >> 1);
    }
}

C++ · adapt the names and types to your problem.

Common pitfalls

  • Not undoing state mutation on backtrack — corrupts sibling branches
  • Forgetting to prune — exponential explosion is the default
  • Recursion depth on Hard problems may hit stack limits; iterative versions help
  • Mutating shared state (a vector, a grid) without restoring it on the way back up

Related patterns

Subsets Graphs Dynamic Programming

Problems (20)

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.