Backtracking

How It Works

Backtracking is depth-first search over a decision tree of partial solutions. At each node you choose one option, explore (recurse) as if that choice were permanent, and then un-choose (undo the choice) before trying the next option, restoring shared state so sibling branches start from a clean slate.

The recursion terminates a branch in one of two ways: it hits a base case where the partial solution is complete (record it into the results) or it hits an invalid state where no completion of the current path could ever be valid (return immediately without recursing further; this is pruning). Pruning is what keeps backtracking from being pure brute force: the earlier you detect that a branch is doomed, the more of the exponential tree you skip.

Because the "un-choose" step mutates a single shared path array or board in place rather than copying it at every level, backtracking uses only O(depth) extra memory for the path itself, even though it explores exponentially many branches.

When To Use It

• "Find all" instead of "find one" or "count": subsets, permutations, combinations, and all valid board configurations require enumerating every possibility, which greedy or DP typically can't do directly.
• Constraint satisfaction over a grid or board: N-Queens, Sudoku, and word search all place pieces one at a time and must check constraints before committing further.
• Partitioning a sequence: palindrome partitioning and combination sum both split an input into pieces where each piece must satisfy a local condition, and an earlier split can invalidate everything downstream.
• A choice can require undoing: if you can imagine needing to "take back" a decision after discovering it doesn't work a few steps later, that's the core signal for backtracking over a purely iterative or greedy approach.
• Small enough input for exponential search: backtracking problems in interviews almost always have small n (often 12 to 20 or fewer) precisely because the time complexity is exponential.

Time & Space Complexity

Complexity depends entirely on the branching factor and depth of the decision tree: subsets and combination-style problems are typically O(2^n), permutation problems are O(n!), and grid-search problems like N-Queens or word search are O(k^n) for some branching factor k bounded by board size. Space is O(n) (or O(rows*cols) for board problems) for the recursion stack and the current partial path, plus whatever space is needed to store all valid results.

// Backtracking template: choose, explore, un-choose
function backtrack(path, choices, result) {
  if (isComplete(path)) {
    result.push([...path]); // record a copy, not a reference
    return;
  }

  for (const choice of choices) {
    if (!isValid(path, choice)) continue; // prune invalid branches early

    path.push(choice);       // choose
    backtrack(path, choices, result); // explore
    path.pop();               // un-choose
  }
}

function solve(input) {
  const result = [];
  backtrack([], input, result);
  return result;
}

Alternative Approaches

• Pruning strategies: sort input first so invalid branches (e.g. combination sums exceeding the target) can be cut early with a break instead of a continue; use bitmasks for "used" tracking (N-Queens column/diagonal sets) instead of arrays for faster constant factors.
• Memoized backtracking: if overlapping subproblems exist (e.g. counting the number of ways rather than listing them), cache results keyed by state to avoid recomputation; this shifts the problem toward dynamic programming.
• Iterative with an explicit stack: some backtracking solutions can be rewritten iteratively using your own stack instead of the call stack, useful when recursion depth risks a stack overflow.
• Branch and bound: for optimization variants (best score rather than all solutions), track a running best and prune any branch whose upper bound can't beat it, turning backtracking into a bounded search.

Common Mistakes

• Forgetting to un-choose: pushing onto a shared path array but never popping leaves stale state that corrupts sibling branches.
• Pushing a reference instead of a copy into results: result.push(path) stores a reference to the same array that keeps mutating; you must copy it ([...path] or path.slice()) at the moment of recording.
• Not pruning early enough: checking validity only at the base case instead of at each step wastes huge amounts of exploration on branches that were already doomed.
• Missing duplicate handling: problems with duplicate input values (like Combination Sum II or Subsets II) need an explicit "skip duplicates at this level" check, or you'll emit duplicate results.
• Off-by-one on the start index: reusing the same index range incorrectly is the most common source of either missing or duplicated combinations.

Pattern Summary

Backtracking is the go-to pattern whenever a problem asks you to enumerate every valid configuration and a decision made early might need to be undone later. The template is always the same: choose, explore, un-choose. The skill that separates a working solution from a slow one is pruning: cutting a doomed branch the moment it's detected saves exponentially more work than catching it only when the path is already complete.