Backtracking

Problems as decision trees

Backtracking problems all share one structure: you build a solution one decision at a time, and each decision has a few options. Picture it as a tree. The root is the empty solution. Each level asks one question. Include this element or not? place the queen in which column?, and each branch is one answer. The leaves of the tree are complete candidate solutions.

Brute force would mean generating every leaf independently, redoing all the shared early decisions each time. Backtracking instead walks the tree with recursion, sharing the common prefix of decisions between sibling branches. It goes deep along one branch, and when that branch is finished (or provably hopeless), it steps back up exactly one level and takes the next branch.

The stepping back is the part that matters. To try the next branch honestly, the state of the world must look exactly like it did before you took the previous branch. That means every change you made on the way down must be reversed on the way back up.

The template: choose, explore, unchoose

Nearly every backtracking solution is three lines wrapped in a loop. Choose: make one of the available decisions, updating your in-progress solution. Explore: recurse to handle all the decisions that come after it. Unchoose: undo the decision so the loop can try the next option from a clean slate.

The in-progress solution is usually a shared, mutable object, a list you add to and remove from, or a board you mark and unmark. Sharing one object instead of copying it at every level is what keeps backtracking fast, and it is exactly why the unchoose step is mandatory. Forget to undo, and the second branch starts polluted with leftovers from the first; this is the single most common backtracking bug.

Here is the skeleton in Java. The base case fires when the solution is complete; the loop iterates over the choices legal at this point.

void backtrack(State state, List<Choice> choices) {
    if (isComplete(state)) {
        recordSolution(state);
        return;
    }
    for (Choice c : choices) {
        state.apply(c);
        backtrack(state, nextChoices(state));
        state.undo(c);
    }
}

Worked example: all subsets of an array

Generate every subset of [1, 2, 3]. There are 2^n subsets because each element poses one yes-or-no decision: in or out. The decision tree has n levels, one per element.

We walk the array with an index. At each index we record the current partial subset as a valid answer, then loop over the remaining elements: choose one (add it to the list), explore everything that can follow it (recurse with the next index), and unchoose it (remove it from the list). The remove call is the backtrack.

Trace it briefly: start with []. Choose 1 giving [1], recurse; choose 2 giving [1,2], recurse; choose 3 giving [1,2,3]. No elements remain, so we return and remove 3, return and remove 2, giving [1] again. Now choose 3 giving [1,3]. Eventually 1 is removed too and the [2 ...] branch begins fresh. Every add is mirrored by exactly one remove, and all 8 subsets appear exactly once. Note the copy when recording a result: the shared list keeps mutating afterward, so we must snapshot it.

void subsets(int[] nums, int start, List<Integer> current,
             List<List<Integer>> result) {
    result.add(new ArrayList<>(current));
    for (int i = start; i < nums.length; i++) {
        current.add(nums[i]);
        subsets(nums, i + 1, current, result);
        current.remove(current.size() - 1);
    }
}

Pruning: skip branches that cannot win

Raw backtracking still visits an exponential tree, so the practical speedups come from pruning: detecting as early as possible that a branch cannot lead to a valid solution, and refusing to enter it. In the maze analogy, pruning is glancing down a corridor, seeing a wall right there, and not bothering to walk in.

Examples: in N-Queens, do not recurse into a square already attacked by a placed queen. In a combination-sum problem where all numbers are positive, stop the moment the running sum exceeds the target. Adding more can only make it worse. Sorting the input first often enables stronger pruning, because once one candidate is too big, all later candidates are too.

Pruning never changes correctness as long as you only cut branches that are provably hopeless; it just avoids wasted exploration. In interviews, stating your pruning rule out loud is an easy way to show depth. Backtracking explores all possibilities, which is sometimes unavoidable, but when subproblems start repeating across branches, there is a better tool, and that is exactly where dynamic programming picks up the story.

Frequently asked