Patterns / Backtracking

Backtracking Pattern

Build a candidate one choice at a time and abandon it the moment it cannot lead to a valid solution.

What it is

Backtracking is a structured, exhaustive search. You make a choice, recurse to extend the partial solution, then undo the choice ("backtrack") to try the next option. Pruning — abandoning a branch as soon as it cannot possibly succeed — is what keeps an exponential search space tractable. It is the workhorse for generating subsets, permutations, and combinations, and for constraint puzzles.

When to use it — the signals

"Generate all …", "find all combinations / permutations / subsets".
Constraint-satisfaction puzzles (N-Queens, Sudoku, word search).
You need every valid arrangement, not just a count or a single answer.

How it works

A representative implementation in Java:

// All subsets via choose / explore / un-choose.
void backtrack(int[] nums, int start, List<Integer> cur, List<List<Integer>> out) {
    out.add(new ArrayList<>(cur));
    for (int i = start; i < nums.length; i++) {
        cur.add(nums[i]);                 // choose
        backtrack(nums, i + 1, cur, out); // explore
        cur.remove(cur.size() - 1);       // un-choose
    }
}

Complexity

Exponential in the worst case (e.g. O(2^n) subsets, O(n!) permutations); pruning cuts the constant dramatically.

Common pitfalls

Forgetting to undo the last choice, corrupting later branches.
Adding a reference to the working list instead of a copy to the results.
Weak or missing pruning, so the search explodes.

Practice problems

Classic problems where this pattern is the intended approach: Subsets, Permutations, Combination Sum, Word Search. Work through them on the Leet Study home page.

← All patterns