Backtracking: The Choose / Explore / Un-choose Template

Backtracking is a recursive problem-solving technique that builds a solution one decision at a time, and as soon as a partial solution can’t possibly lead to a valid answer, it undoes the last decision and tries another. It’s a smart, organized brute force: explore every option, but abandon dead ends early. Almost all backtracking solutions follow one rhythm — choose, explore, un-choose — and once you see it, problems like subsets, permutations, and N-Queens all look the same.

The mental model: a decision tree

Think of every choice as a branch. At each step you pick an option (go down a branch), recurse to make the next choice, then come back up and pick a different option. Backtracking is a depth-first walk over this tree of choices, recording solutions at the leaves.

The choose / explore / un-choose template

This is the skeleton you adapt to almost any backtracking problem:

void backtrack(State& state, Result& result) {
    if (isComplete(state)) {        // reached a full solution
        result.record(state);
        return;
    }
    for (auto& option : choices(state)) {
        if (!isValid(option, state)) continue; // prune dead ends
        state.apply(option);        // 1. CHOOSE
        backtrack(state, result);   // 2. EXPLORE
        state.undo(option);         // 3. UN-CHOOSE (backtrack)
    }
}

void backtrack(State state, Result result) {
    if (isComplete(state)) {        // reached a full solution
        result.record(state);
        return;
    }
    for (Option option : choices(state)) {
        if (!isValid(option, state)) continue; // prune dead ends
        state.apply(option);        // 1. CHOOSE
        backtrack(state, result);   // 2. EXPLORE
        state.undo(option);         // 3. UN-CHOOSE (backtrack)
    }
}

function backtrack(state, result) {
  if (isComplete(state)) {          // reached a full solution
    result.record(state);
    return;
  }
  for (const option of choices(state)) {
    if (!isValid(option, state)) continue; // prune dead ends
    state.apply(option);            // 1. CHOOSE
    backtrack(state, result);       // 2. EXPLORE
    state.undo(option);             // 3. UN-CHOOSE (backtrack)
  }
}

def backtrack(state, result):
    if is_complete(state):          # reached a full solution
        result.append(state.snapshot())
        return
    for option in choices(state):
        if not is_valid(option, state):
            continue                # prune dead ends
        state.apply(option)         # 1. CHOOSE
        backtrack(state, result)    # 2. EXPLORE
        state.undo(option)          # 3. UN-CHOOSE (backtrack)

A concrete example: all subsets

Generating every subset of [1, 2, 3] is backtracking in its purest form. At each index you make one binary choice: include this element or skip it. The “un-choose” step is removing what you added so the next branch starts clean.

void subsets(const std::vector<int>& nums, int i,
             std::vector<int>& current,
             std::vector<std::vector<int>>& result) {
    if (i == (int)nums.size()) {
        result.push_back(current);   // record one complete subset
        return;
    }
    current.push_back(nums[i]);      // CHOOSE: include nums[i]
    subsets(nums, i + 1, current, result); // EXPLORE
    current.pop_back();              // UN-CHOOSE: remove it
    subsets(nums, i + 1, current, result); // EXPLORE skipping nums[i]
}

void subsets(int[] nums, int i, List<Integer> current,
             List<List<Integer>> result) {
    if (i == nums.length) {
        result.add(new ArrayList<>(current)); // record a copy
        return;
    }
    current.add(nums[i]);            // CHOOSE: include nums[i]
    subsets(nums, i + 1, current, result); // EXPLORE
    current.remove(current.size() - 1);    // UN-CHOOSE
    subsets(nums, i + 1, current, result); // EXPLORE skipping nums[i]
}

function subsets(nums, i, current, result) {
  if (i === nums.length) {
    result.push([...current]);       // record a copy
    return;
  }
  current.push(nums[i]);             // CHOOSE: include nums[i]
  subsets(nums, i + 1, current, result); // EXPLORE
  current.pop();                     // UN-CHOOSE
  subsets(nums, i + 1, current, result); // EXPLORE skipping nums[i]
}

def subsets(nums, i, current, result):
    if i == len(nums):
        result.append(current[:])    # record a copy
        return
    current.append(nums[i])          # CHOOSE: include nums[i]
    subsets(nums, i + 1, current, result)  # EXPLORE
    current.pop()                    # UN-CHOOSE
    subsets(nums, i + 1, current, result)  # EXPLORE skipping nums[i]

For beginners: Notice we copy current when recording a result. current is one shared, mutable buffer that keeps changing as we explore — store it directly and every saved “solution” would point to the same buffer and end up empty or wrong. Always snapshot.

Pruning: the reason backtracking beats brute force

The power move is the isValid check that skips branches early. If a partial choice already violates a constraint, you cut the entire subtree below it instead of generating useless candidates. Good pruning is what makes N-Queens or Sudoku feasible. Without pruning, backtracking degrades to plain exhaustive search.

Complexity

Backtracking explores a tree of choices, so its cost reflects the number of candidates. Subsets: O(2ⁿ) (each element in or out). Permutations: O(n!). These are exponential by nature — backtracking’s job is to make the constant factor small via pruning, not to change the class.

Going deeper: The recursion depth equals the solution length, so stack space is O(depth) on top of whatever you store. When the same subproblems repeat (not just the same shape), backtracking shades into dynamic programming.

Next: apply the template to real problems in common backtracking problems, or test yourself on the recursion exercises.