Backtracking

At a glance

The instinct

When the output is "every valid X", the answer itself can be exponential in size, so no clever trick avoids enumeration - the job is to enumerate cleanly and prune early. Picture a decision tree: each level makes one choice (take this number, place a queen in this column, cut the string here). Depth-first search walks the tree, keeps a single mutable path, and restores it after each child so siblings start from the same state.

Subsets, Permutations and Combination Sum are the three skeletons; almost every other backtracking problem, including N-Queens and Word Search, is one of them with extra constraints.

Recognise it

Not this pattern if...

• Only a count or a best value is asked and subproblems repeat - that is DP (counting coin-change ways, minimum coins).
• n is around 10^5 - exponential search is impossible; look for greedy, DP or a formula.
• You need a shortest path in a grid - BFS finds it without exploring every path.
• You only need reachability in a graph - plain DFS with a permanent visited set, no undo.

Memory hack

Analogy - the maze and the ball of string. You explore a maze while unrolling string behind you. At each fork you try one corridor. At a dead end you wind the string back to the last fork and try the next corridor. Pruning is a sign at a corridor entrance saying "dead end ahead" - you don't even walk in.

Say it out loud:

1. "My state is the path so far; the choices at each level are ___."
2. "When ___ I record a copy of the path (and stop, or keep going for subsets)."
3. "I prune when ___, skip duplicates by sorting and skipping equal siblings, and undo every change after the recursive call."

How it works

Decision tree for Subsets of [1, 2, 3] using a start index. Every node is a valid subset, so all 8 get recorded. Because each level only offers elements after the last one chosen, [2, 1] can never appear as a duplicate of [1, 2].

flowchart TD
  R["[ ]"] --> A["[1]"]
  R --> B["[2]"]
  R --> C["[3]"]
  A --> D["[1, 2]"]
  A --> E["[1, 3]"]
  D --> F["[1, 2, 3]"]
  B --> G["[2, 3]"]

The other families change only what a level may choose: permutations scan every index not yet used, partitioning chooses the end of the next piece, and grid search chooses one of four neighbours.

Java template

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class BacktrackingTemplate {
    // Combinations family (Combination Sum II shape). Sort so duplicates sit together and pruning works.
    static List<List<Integer>> combinations(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> out = new ArrayList<>();
        dfs(nums, 0, target, new ArrayList<>(), out);
        return out;
    }

    static void dfs(int[] nums, int start, int remain, List<Integer> path, List<List<Integer>> out) {
        if (remain == 0) { out.add(new ArrayList<>(path)); return; }  // goal: store a COPY
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) continue;         // skip duplicate siblings
            if (nums[i] > remain) break;                                // prune (positive, sorted input)
            path.add(nums[i]);                                          // choose
            dfs(nums, i + 1, remain - nums[i], path, out);              // explore; pass i if reuse is allowed
            path.remove(path.size() - 1);                               // un-choose
        }
    }

    // Permutations family: every position may take any element not yet used.
    static void permute(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> out) {
        if (path.size() == nums.length) { out.add(new ArrayList<>(path)); return; }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true;  path.add(nums[i]);                         // choose
            permute(nums, used, path, out);                             // explore
            used[i] = false; path.remove(path.size() - 1);              // un-choose
        }
    }
}

For Subsets, drop the target check and add a copy of path at the top of every call. For grid problems like Word Search, "choose" means overwriting the cell with a marker and "un-choose" means restoring the original letter.

Complexity

Pruning rarely changes the worst-case bound, but in practice it is the difference between passing and timing out.

Variations

• Subsets - record at every node. Subsets.
• Combinations with a target - reuse allowed means recurse with i (Combination Sum); use-once with duplicate input means i + 1 plus sibling skipping (Combination Sum II).
• Permutations - used[] array; with duplicates, sort and skip nums[i] == nums[i-1] && !used[i-1]. Permutations.
• Cartesian product - each position chooses from its own list. Letter Combinations of a Phone Number.
• Generation with counters - add ( while open < n, add ) while close < open. Generate Parentheses.
• Partitioning - choose the next cut; precompute a palindrome table. Palindrome Partitioning.
• Constraint placement - sets for columns and both diagonals (r - c, r + c). N-Queens.
• Grid path search - mark, explore four directions, unmark. Word Search.

Common mistakes

• Forgetting to undo one piece of state - the used flag, the grid marker, or a StringBuilder's length.
• Using i > 0 instead of i > start for duplicate skipping, which wrongly drops valid answers such as [1, 1, 6].
• Recursing with i + 1 when reuse is allowed (missing answers), or with i when it is not (infinite reuse).
• Pruning with break on unsorted input or with negative numbers - later candidates might still fit.
• Building strings with + at every level; a shared StringBuilder with setLength is cheaper.

All practice problems

9 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.