Backtracking

Build, check, undo

[[backtracking|Backtracking]] is a structured way to explore all the possibilities for a problem by building a solution incrementally. At each step you make a tentative choice, recurse to extend it, and if that path dead-ends, you undo the choice and try a different one. Think of walking a maze with a ball of string: you advance, and whenever you hit a wall, you reel the string back to the last junction and take another turn.

Backtracking is really a depth-first search over a decision tree, powered by recursion. Each node of the tree is a partial solution; each branch is one possible next choice; each leaf is a complete candidate. The `undo` step — restoring the state to what it was before the choice — is what lets a single function explore the whole tree without leaving a mess behind.

Worked example: all permutations

Let's generate every ordering of `[1, 2, 3]`. At each level of the recursion we pick one unused number, mark it used, recurse to fill the rest, then unmark it. The marking and unmarking *is* the choose/un-choose pair.

                       [ ]                 <- nothing chosen yet
          /             |             \
        [1]            [2]            [3]
       /   \          /   \          /   \
    [1,2] [1,3]    [2,1] [2,3]    [3,1] [3,2]
      |     |        |     |        |     |
  [1,2,3][1,3,2] [2,1,3][2,3,1] [3,1,2][3,2,1]   <- 6 leaves = 3! perms

#include <vector>

void permute(std::vector<int>& nums, std::vector<bool>& used,
             std::vector<int>& path, std::vector<std::vector<int>>& out) {
    if (path.size() == nums.size()) { out.push_back(path); return; } // leaf
    for (int i = 0; i < (int)nums.size(); i++) {
        if (used[i]) continue;          // skip already-chosen numbers
        used[i] = true; path.push_back(nums[i]);   // CHOOSE
        permute(nums, used, path, out);            // EXPLORE
        path.pop_back(); used[i] = false;          // UN-CHOOSE
    }
}

Subsets, and the power of pruning

Subsets are even simpler: for each element, the only decision is *in or out.* That's a binary choice tree of depth `n`, giving 2^n subsets. Backtracking walks it by including an element (choose), recursing, then excluding it (un-choose). But the real reason backtracking beats brute force is pruning: the moment a partial solution is provably hopeless, you stop and back up — chopping off an entire subtree of wasted work.

N-queens is the showcase. Place `n` queens on an `n×n` board so none attack each other. The naive count of arrangements is astronomical, but backtracking places queens one row at a time and *prunes* the instant a new queen shares a column or diagonal with one already placed. That single check throws away the vast majority of the tree before it's ever explored — turning an impossible search into a tractable one.

The general template

Almost every backtracking solution fits one shape. Once you've written it a few times, new problems become a matter of filling in the blanks: what's a complete solution, what choices are available, and what makes a choice invalid (so you can prune).

1. If the partial solution is complete, record it and return (you've reached a leaf).
2. Loop over the available choices for the next position.
3. Prune: if a choice is clearly invalid, skip it now — don't even recurse.
4. CHOOSE: apply the choice to the partial solution.
5. EXPLORE: recurse to extend it.
6. UN-CHOOSE: undo the choice before trying the next one.

If this template feels familiar, good — it's the same depth-first descent you saw traversing trees and graphs, now applied to a tree of *decisions* rather than a tree of *data*. Recursion, DFS, and backtracking are three faces of one idea: go deep, then come back.