The Backtracking Pattern: Template & When to Use It

The backtracking pattern explores all valid configurations by building a candidate one choice at a time, and undoing (“backtracking on”) each choice before trying the next — a depth-first search over the tree of decisions, pruned whenever a partial choice can’t lead to a solution. It’s the go-to for “generate all X” and constraint-satisfaction problems. This page recaps the signal and the universal template.

For the topic treatment, see backtracking: introduction and common backtracking problems.

The signal: when to recognize it

• “Generate all subsets / permutations / combinations / partitions.”
• “Find all ways / paths / arrangements that satisfy a constraint” (N-Queens, Sudoku, word search).
• The answer is built from a sequence of choices, and you must explore every branch (no greedy shortcut, no overlapping-subproblem reuse).
• The input is small — backtracking is often exponential, so constraints like n ≤ 20 are a hint.

For beginners: Backtracking is “try a choice, recurse, then take it back.” Picture exploring a maze: walk down a path, and if it’s a dead end, return to the last junction and try another. The “take it back” step is what makes the same data structure reusable across branches.

The universal template

Every backtracking solution has the same skeleton: a base case that records a complete candidate, a loop over choices, and a choose / recurse / un-choose body. Here it generates all subsets of a list (the power set).

#include <vector>
// Backtracking: collect all subsets (the power set) of nums.
void backtrack(const std::vector<int>& nums, int start,
               std::vector<int>& current,
               std::vector<std::vector<int>>& result) {
    result.push_back(current);                 // record this subset
    for (int i = start; i < (int)nums.size(); i++) {
        current.push_back(nums[i]);            // choose
        backtrack(nums, i + 1, current, result); // recurse on the rest
        current.pop_back();                    // un-choose (backtrack)
    }
}
std::vector<std::vector<int>> subsets(const std::vector<int>& nums) {
    std::vector<std::vector<int>> result;
    std::vector<int> current;
    backtrack(nums, 0, current, result);
    return result;
}

import java.util.ArrayList;
import java.util.List;
// Backtracking: collect all subsets (the power set) of nums.
void backtrack(int[] nums, int start, List<Integer> current,
               List<List<Integer>> result) {
    result.add(new ArrayList<>(current));      // record this subset
    for (int i = start; i < nums.length; i++) {
        current.add(nums[i]);                  // choose
        backtrack(nums, i + 1, current, result); // recurse on the rest
        current.remove(current.size() - 1);    // un-choose (backtrack)
    }
}
List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), result);
    return result;
}

// Backtracking: collect all subsets (the power set) of nums.
function subsets(nums) {
  const result = [];
  const current = [];
  function backtrack(start) {
    result.push([...current]);          // record this subset
    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]);            // choose
      backtrack(i + 1);                 // recurse on the rest
      current.pop();                    // un-choose (backtrack)
    }
  }
  backtrack(0);
  return result;
}

# Backtracking: collect all subsets (the power set) of nums.
def subsets(nums):
    result = []
    current = []
    def backtrack(start):
        result.append(current[:])       # record this subset
        for i in range(start, len(nums)):
            current.append(nums[i])     # choose
            backtrack(i + 1)            # recurse on the rest
            current.pop()               # un-choose (backtrack)
    backtrack(0)
    return result

Adapting the template

• Permutations: loop over all indices (not from start), skip those already used (track a used[] array), and record when current.size() == n.
• Combinations of size k: stop and record only when current.size() == k, recurse from i + 1.
• Constraint puzzles (N-Queens, Sudoku): add an if (isValid(choice)) guard before “choose” to prune branches early — the single biggest speedup.

Going deeper: Pruning is the whole game. The naive tree has exponentially many leaves; a good isValid check cuts off entire subtrees before you descend into them, turning an impossible search into a feasible one.

Complexity

Backtracking is inherently exponential: there are 2ⁿ subsets, n! permutations, and so on, and you must touch each valid one. Subsets is O(n · 2ⁿ) time (copying each of 2ⁿ subsets) and O(n) recursion depth (extra space, excluding the output). Pruning lowers the practical cost but not the worst-case bound.

Common pitfalls

• Forgetting to un-choose. Without the pop/pop_back/remove, current leaks state into sibling branches and the output is wrong.
• Storing a reference instead of a copy. Record new ArrayList<>(current) / current[:] / [...current] — otherwise every recorded “subset” points at the same mutating list.
• No pruning on constraint problems. Without an early validity check, the search explodes.
• Duplicates. With repeated input values, sort first and skip equal siblings to avoid duplicate results.

Practice

Drill it in the recursion & backtracking exercises. Backtracking builds directly on recursion; when subproblems start overlapping and you only need an optimal count/value (not every arrangement), switch to dynamic programming.