Backtracking

Overview

Backtracking builds solutions one choice at a time and abandons (backtracks from) a partial solution as soon as it cannot lead to a valid answer. It is depth-first search over a tree of decisions: each level is a decision, each branch is an option, and each leaf is a complete candidate.

Every backtracking solution follows the same three-step template: choose an option, explore recursively, then un-choose (undo the change) so the next option starts from a clean state. Pruning, meaning cutting branches early when constraints are already violated, is what turns exponential brute force into something practical.

When to use it

• The problem asks for all solutions: all subsets, permutations, combinations, paths, or arrangements.
• Constraint satisfaction: Sudoku, N-Queens, word search, crosswords.
• Input size is small (n around 10 to 20), a strong hint that exponential time is expected.
• You can check partway through whether a partial solution is still valid (pruning).

Problem patterns it solves

Where it is used in real software

Key terms

State

The partial solution being built, such as the current path.

Choice

An option added to the state at the current level.

Undo / backtrack

Reverse the choice after exploring it (pop, unmark, restore).

Pruning

Stop exploring a branch that can no longer lead to a valid answer.

Decision tree

The tree of all choice sequences that backtracking explores.

The universal template

1. 1
   Define the state and the goal

   What does a partial solution look like, and when is it complete?

2. 2
   Record complete solutions

   When the goal is reached, save a copy of the state.

3. 3
   Loop over the available choices

   The options at this level, often starting from an index to avoid repeats.

4. 4
   Prune invalid choices

   Skip options that break a constraint (sum too big, duplicate, conflict).

5. 5
   Choose, explore, un-choose

   Add the choice, recurse, then remove it so the state is clean for the next option.

Combination Sum: candidates [2, 3, 6, 7], target 7

Each number may be reused; start index prevents duplicate orderings

Results: [2, 2, 3] and [7]. Because candidates are sorted, once one option overshoots, every larger option at that level can be skipped with a break.

Implementation

1function combinationSum(candidates, target) {2  candidates.sort((a, b) => a - b);3  const result = [], path = [];4  function backtrack(start, remaining) {5    if (remaining === 0) {6      result.push([...path]); // copy the state7      return;8    }9    for (let i = start; i < candidates.length; i++) {10      if (candidates[i] > remaining) break; // prune: sorted, so later ones are bigger11      path.push(candidates[i]);              // choose12      backtrack(i, remaining - candidates[i]); // explore (i, not i + 1: reuse allowed)13      path.pop();                            // un-choose14    }15  }16  backtrack(0, target);17  return result;18}19 20// 79. Word Search: mark cells in place, restore on return21function exist(board, word) {22  const rows = board.length, cols = board[0].length;23  function dfs(r, c, i) {24    if (i === word.length) return true;25    if (r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] !== word[i]) return false;26    const saved = board[r][c];27    board[r][c] = "#";28    const found = dfs(r + 1, c, i + 1) || dfs(r - 1, c, i + 1) || dfs(r, c + 1, i + 1) || dfs(r, c - 1, i + 1);29    board[r][c] = saved;30    return found;31  }32  for (let r = 0; r < rows; r++) for (let c = 0; c < cols; c++) if (dfs(r, c, 0)) return true;33  return false;34}35 36// 131. Palindrome Partitioning37function partition(s) {38  const result = [], path = [];39  const isPal = (l, r) => { while (l < r) if (s[l++] !== s[r--]) return false; return true; };40  function backtrack(start) {41    if (start === s.length) { result.push([...path]); return; }42    for (let end = start; end < s.length; end++) {43      if (!isPal(start, end)) continue;44      path.push(s.slice(start, end + 1));45      backtrack(end + 1);46      path.pop();47    }48  }49  backtrack(0);50  return result;51}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Saving a reference to the path instead of a copy.

  Fix: result.push([...path]) or new ArrayList<>(path); otherwise every saved result changes later.

• Forgetting to undo the choice.

  Fix: Every push needs a matching pop; every mark needs an unmark.

• Duplicate results with repeated values.

  Fix: Sort, then skip c[i] === c[i - 1] when i > start.

• Using i + 1 vs i incorrectly.

  Fix: Recurse with i when reuse is allowed and i + 1 when each item is used once.

Interview questions

Practice problems