Chapter 11 — Backtracking

Connect Backward

Chapter 4a introduced the include/exclude pattern for generating all subsets:

function subsets(nums, i, current, result) {
  if (i === nums.length) { result.push([...current]); return; }
  current.push(nums[i]);   // include
  subsets(nums, i + 1, current, result);
  current.pop();           // exclude — this pop IS backtracking
  subsets(nums, i + 1, current, result);
}

That current.pop() before the second recursive call — that is backtracking. You chose something, explored where that choice leads, then undid the choice before trying the alternative. Chapter 11 names this pattern, generalizes it with constraints, and shows you how to prune the decision tree when a partial solution can never become valid.

Chapter 10 built physical intuition for tree traversal. A backtracking algorithm traverses an implicit tree — a tree that exists in the structure of the problem, not in memory. Backtracking is DFS on a decision tree.

1. The Physical Reality: A Decision Tree

You are making a sequence of decisions. Each decision branches the tree. At each node you have a partial solution. A leaf node is either a complete valid solution (collect it) or a dead end (stop).

For subsets([1, 2, 3]), the decision tree looks like this:

                    []
           /                  \
        [1]                   []
       /    \               /    \
    [1,2]  [1]         [2]      []
    / \    / \         / \      / \
[1,2,3][1,2][1,3][1] [2,3][2] [3] []

Every path from root to leaf is one subset. There are 8 leaves, 8 subsets. The tree has 2^n leaves for n elements.

For combinations(4, 2) (pick 2 from 1..4, order doesn't matter), the tree is smaller:

            []
         /  |  |  \
       [1] [2] [3] [4]
       / \   \
   [1,2][1,3] [2,3]
      [1,4]  [2,4]
              [3,4]

The pruning rule: when you've already picked [3], you don't explore [3,1] or [3,2] because order doesn't matter — you only look at numbers after 3. This pruning cuts the tree substantially.

2. The Three-Step Template

Every backtracking algorithm has exactly three steps at each node:

CHOOSE → EXPLORE → UNCHOOSE

function backtrack(state, choices) {
  if (isComplete(state)) {
    collect(state);
    return;
  }
  
  for (const choice of choices) {
    if (isValid(state, choice)) {
      makeChoice(state, choice);   // CHOOSE
      backtrack(state, nextChoices(state, choice));  // EXPLORE
      undoChoice(state, choice);   // UNCHOOSE (backtrack)
    }
  }
}

The UNCHOOSE step is the critical one. It restores the state to exactly what it was before the choice. This is why backtracking uses a single mutable array (current) instead of creating a new array at every node — you can add to it (choose), recurse, then pop from it (unchoose). Creating a new array would also work but costs O(n) per node.

3. Four Problem Types

Almost every backtracking problem is one of four shapes:

Understanding which shape your problem is tells you which pruning strategy to use.

4. Subsets — The Foundation

Problem: generate all subsets of [1, 2, 3].

The decision at each step: for element at index i, include it or not.

function subsets(nums) {
  const result = [];
  
  function backtrack(i, current) {
    result.push([...current]);  // every node is a valid subset
    
    for (let j = i; j < nums.length; j++) {
      current.push(nums[j]);    // CHOOSE
      backtrack(j + 1, current); // EXPLORE (only look forward — no duplicates)
      current.pop();             // UNCHOOSE
    }
  }
  
  backtrack(0, []);
  return result;
}

This is the iterative formulation. It differs slightly from Chapter 4a's recursive formulation but produces identical results. The key insight: j starts at i, not at 0. This prevents [2, 1] from appearing when [1, 2] already exists — order doesn't matter for subsets.

Call trace for [1, 2]:

backtrack(0, [])       → collect []
  push 1 → backtrack(1, [1]) → collect [1]
    push 2 → backtrack(2, [1,2]) → collect [1,2], no more to pick
    pop 2
  pop 1
  push 2 → backtrack(2, [2]) → collect [2], no more to pick
  pop 2

Result: [], [1], [1,2], [2] — all 4 subsets of [1, 2]. ✓

5. Combinations — Adding a Constraint

Problem: given n and k, return all combinations of k numbers from 1..n.

The decision tree is the same as subsets but we only collect leaves where current.length === k.

function combine(n, k) {
  const result = [];
  
  function backtrack(start, current) {
    if (current.length === k) {
      result.push([...current]);
      return;  // stop going deeper — no combination needs more than k elements
    }
    
    // Pruning: we need k - current.length more numbers.
    // The largest possible start that can still give us enough is:
    // n - (k - current.length) + 1
    for (let i = start; i <= n - (k - current.length) + 1; i++) {
      current.push(i);
      backtrack(i + 1, current);
      current.pop();
    }
  }
  
  backtrack(1, []);
  return result;
}

The loop bound i <= n - (k - current.length) + 1 is a pruning optimization. If we need 2 more numbers and only have [5, 6] left from n = 6, we can skip starting at 5 because we can't fill the remaining slot. Without this, the code still works — it just explores dead branches.

6. Combination Sum — Unlimited Reuse

Problem: given candidates [2, 3, 6, 7] and target 7, find all combinations that sum to 7. Each number can be used unlimited times.

This is the problem explicitly asked at Zepto and Razorpay.

What do I have? Array of positive integers candidates, target integer.
What do I want? All unique combinations that sum to target. Numbers can repeat.
What is the brute force? Try every possible multiset of candidates and check if it sums to target.
Where is the waste? Once remaining < 0, we've overshot — stop. Also, always advance index forward to avoid [2, 2, 3] and [3, 2, 2] as separate answers.

function combinationSum(candidates, target) {
  const result = [];
  candidates.sort((a, b) => a - b);  // sort to enable early stopping
  
  function backtrack(start, current, remaining) {
    if (remaining === 0) {
      result.push([...current]);
      return;
    }
    
    for (let i = start; i < candidates.length; i++) {
      if (candidates[i] > remaining) break;  // sorted — all later ones also too big
      
      current.push(candidates[i]);
      backtrack(i, current, remaining - candidates[i]);  // i not i+1: allow reuse
      current.pop();
    }
  }
  
  backtrack(0, [], target);
  return result;
}

The key difference from Combination Sum vs regular combinations: backtrack(i, ...) not backtrack(i + 1, ...). Passing i means "I can pick candidates[i] again". Passing i + 1 means "I can't pick this element again".

Full dry run on candidates = [2, 3, 6, 7], target = 7:

backtrack(0, [], 7)
  pick 2 → backtrack(0, [2], 5)
    pick 2 → backtrack(0, [2,2], 3)
      pick 2 → backtrack(0, [2,2,2], 1)
        pick 2 → remaining = -1, 2 > 1, BREAK
        → dead end
      pop 2
      pick 3 → backtrack(1, [2,2,3], 0)
        remaining = 0 → COLLECT [2,2,3] ✓
      pop 3
      pick 6 → 6 > 1, BREAK
    pop 2
    pick 3 → backtrack(1, [2,3], 2)
      pick 3 → 3 > 2, BREAK
      → dead end
    pop 3
    pick 6 → 6 > 5, BREAK
  pop 2
  pick 3 → backtrack(1, [3], 4)
    pick 3 → backtrack(1, [3,3], 1)
      pick 3 → 3 > 1, BREAK
      → dead end
    pop 3
    pick 6 → 6 > 4, BREAK
  pop 3
  pick 6 → backtrack(2, [6], 1)
    pick 6 → 6 > 1, BREAK
  pop 6
  pick 7 → backtrack(3, [7], 0)
    remaining = 0 → COLLECT [7] ✓
  pop 7

Result: [[2,2,3], [7]]. ✓

Time complexity: O(n^(t/m)) where t is target and m is min candidate. This is the height of the tree (t/m) with branching factor n. Pruning reduces practical runtime significantly.

7. Permutations — Order Matters

Problem: given [1, 2, 3], return all permutations.

Now order matters. [1, 2, 3] and [1, 3, 2] are different answers. The decision at each step: pick any unused element.

What do I have? Array of distinct integers.
What do I want? All orderings of all elements.
Brute force? For each position, try every unused element.
Where is waste? None — we must generate all n! permutations. No pruning possible.

function permute(nums) {
  const result = [];
  const used = new Array(nums.length).fill(false);
  
  function backtrack(current) {
    if (current.length === nums.length) {
      result.push([...current]);
      return;
    }
    
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      
      used[i] = true;
      current.push(nums[i]);
      backtrack(current);
      current.pop();
      used[i] = false;
    }
  }
  
  backtrack([]);
  return result;
}

The used boolean array tracks which elements are currently in the partial permutation. When we backtrack, we set used[i] = false to make the element available again for other branches.

Why a used array instead of slicing? Slicing creates O(n) work per node. The used array gives O(1) check. For n=8, this is the difference between 40,320 slice operations vs 40,320 boolean flips.

Partial dry run on [1, 2, 3]:

backtrack([])
  i=0: use 1 → backtrack([1])
    i=1: use 2 → backtrack([1,2])
      i=2: use 3 → backtrack([1,2,3]) → COLLECT [1,2,3]
      unuse 3
    unuse 2
    i=2: use 3 → backtrack([1,3])
      i=1: use 2 → backtrack([1,3,2]) → COLLECT [1,3,2]
      unuse 2
    unuse 3
  unuse 1
  i=1: use 2 → backtrack([2])
    ... → [2,1,3], [2,3,1]
  i=2: use 3 → backtrack([3])
    ... → [3,1,2], [3,2,1]

Total: 6 = 3! permutations. ✓

Time complexity: O(n × n!) — there are n! permutations, each of length n to copy.

8. N-Queens — Constraint Satisfaction

Problem: place n queens on an n×n chessboard so no two queens attack each other.

Two queens attack each other if they share a row, column, or diagonal.

What do I have? Board size n.
What do I want? All valid placements of n queens.
Brute force? Try all ways to place n queens on n² squares. n=8 gives C(64,8) ≈ 4 billion.
Where is waste? Place one queen per row (since no two queens can share a row, exactly one must go in each row). Now brute force is 8^8 ≈ 16 million. Apply column/diagonal constraints as we go: prune immediately when a placement is invalid.

The clever observation: represent column occupation and both diagonals using sets.

For a queen at (row, col):
  - top-left to bottom-right diagonal: (row - col) is constant along this diagonal
  - top-right to bottom-left diagonal: (row + col) is constant along this diagonal

function solveNQueens(n) {
  const result = [];
  const cols = new Set();
  const diag1 = new Set();  // row - col (top-left to bottom-right)
  const diag2 = new Set();  // row + col (top-right to bottom-left)
  
  const board = Array.from({ length: n }, () => Array(n).fill('.'));
  
  function backtrack(row) {
    if (row === n) {
      result.push(board.map(r => r.join('')));
      return;
    }
    
    for (let col = 0; col < n; col++) {
      if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) {
        continue;  // PRUNE: invalid placement
      }
      
      // CHOOSE
      cols.add(col);
      diag1.add(row - col);
      diag2.add(row + col);
      board[row][col] = 'Q';
      
      // EXPLORE
      backtrack(row + 1);
      
      // UNCHOOSE
      cols.delete(col);
      diag1.delete(row - col);
      diag2.delete(row + col);
      board[row][col] = '.';
    }
  }
  
  backtrack(0);
  return result;
}

Why row - col for diagonal? Consider the diagonal containing (0,0), (1,1), (2,2). For each, row - col = 0. Any two cells on the same top-left-to-bottom-right diagonal have the same row - col. So checking diag1.has(row - col) answers "is there already a queen on this diagonal?" in O(1).

Why row + col for the other diagonal? Consider (0,2), (1,1), (2,0). For each, row + col = 2. ✓

N=4 dry run (first valid solution):

row 0: try col 0 → place Q at (0,0), cols={0}, d1={0}, d2={0}
row 1: try col 0 → col 0 taken, skip
        try col 1 → diag2: 1+1=2 ≠ 0. diag1: 1-1=0, d1 has 0 → skip
        try col 2 → cols={0}, diag1: 1-2=-1, diag2: 1+2=3, all clear → place Q
row 2: try col 0 → col 0 taken, skip
        try col 1 → diag2: 2+1=3, d2 has 3 → skip
        try col 2 → col 2 taken, skip
        try col 3 → diag1: 2-3=-1, d1 has -1 → skip
        → NO valid column at row 2. BACKTRACK.
row 1: pop Q at (1,2). try col 3 → diag1: 1-3=-2, diag2: 1+3=4, clear → place
row 2: try col 0 → diag2: 2+0=2, d2 has {0,4}. No. diag1: 2-0=2. No. cols: no 0. 
        → all clear → place Q at (2,0)
row 3: try col 0 → col 0 taken
        try col 1 → diag1: 3-1=2, d1 has 2 → skip
        try col 2 → diag2: 3+2=5? Not in {0,4}. diag1: 3-2=1, not in {0,-2,2}. cols: no 2.
        → place Q at (3,2)
row 4 = n → COLLECT
  . Q . .
  . . . Q
  Q . . .
  . . Q .

This is a valid 4-queens solution. ✓

For n=8, there are 92 solutions.

Time complexity: O(n!) in the worst case but pruning makes practical runtime much better. Each row has n choices, but constraints eliminate most of them.

9. The Deduplication Pattern

When input has duplicate elements, naive backtracking generates duplicate output combinations. The fix:

1. Sort the input first.
2. Skip an element if it equals the previous element AND the previous element was not used in the current branch.

// For Subsets II / Combination Sum II
for (let i = start; i < candidates.length; i++) {
  if (i > start && candidates[i] === candidates[i - 1]) {
    continue;  // skip duplicate at this level of the tree
  }
  // ... normal backtrack
}

Why i > start not i > 0? The condition i > 0 && candidates[i] === candidates[i-1] would also skip the second occurrence when it appears at a different position in the current combination — which is wrong. We only want to skip it when it appears at the same decision level (same start). The condition i > start means "this is not the first element we're considering at this level".

Example: nums = [1, 1, 2], subsets

Without deduplication: [], [1], [1,1], [1,1,2], [1,2], [1], [1,2], [2] — [1] and [1,2] appear twice.

With deduplication (sort, then if (i > start && nums[i] === nums[i-1]) continue):

[], [1], [1,1], [1,1,2], [1,2], [2]

Six unique subsets. ✓

10. Why Is Backtracking Slow? When Is It Fast Enough?

Theoretical upper bound:

• Subsets: O(2^n) — n binary decisions
• Permutations: O(n!) — n! orderings
• Combinations: O(C(n,k)) — but exploration is O(2^n) without pruning

Practical reality: These are the upper bounds without pruning. Good pruning can reduce actual nodes visited by 90%+. N-Queens with n=8: theoretical 8^8 = 16M, actual nodes visited ≈ 2000.

When backtracking is the answer: When n is small (n ≤ 20 for 2^n, n ≤ 10 for n!). Almost every backtracking problem at interviews has n ≤ 15.

When it's too slow: Large n. DP often solves the "count" version (how many valid combinations?) in polynomial time, while backtracking solves the "enumerate" version (what are all the combinations?).

11. Mental Model: When to Reach for Backtracking

Reach for backtracking when:

1. You need to enumerate all valid solutions (not just count them or find one).
2. You're making a sequence of choices where each choice constrains future choices.
3. You can detect early when a partial solution is already invalid (enabling pruning).

The mental model: you're exploring a forest by walking DFS, but you turn around early when you see the path is blocked. Instead of exploring the whole forest (brute force), you skip entire subtrees.

Signal phrases in problems: "return all", "find all combinations/permutations/subsets", "all valid placements". If you see "all" and the search space is a sequence of choices, it's backtracking.

12. The Word Search Pattern — 2D Backtracking

Problem: given a grid and a word, return true if the word exists as adjacent (up/down/left/right) cells.

This is backtracking on a 2D grid. The "choose" step is visiting a cell; the "unchoose" step is marking it as unvisited.

function exist(board, word) {
  const rows = board.length, cols = board[0].length;
  
  function backtrack(r, c, i) {
    if (i === word.length) return true;
    if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
    if (board[r][c] !== word[i]) return false;
    if (board[r][c] === '#') return false;  // already visited
    
    const temp = board[r][c];
    board[r][c] = '#';  // CHOOSE: mark visited
    
    const found = backtrack(r+1, c, i+1) ||
                  backtrack(r-1, c, i+1) ||
                  backtrack(r, c+1, i+1) ||
                  backtrack(r, c-1, i+1);
    
    board[r][c] = temp;  // UNCHOOSE: restore
    return found;
  }
  
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (backtrack(r, c, 0)) return true;
    }
  }
  return false;
}

We mark cells with '#' to prevent reusing the same cell in a single path (choose). We restore to temp when backtracking (unchoose). This is O(1) space instead of maintaining a separate visited set.

Time complexity: O(rows × cols × 4^L) where L is word length. From each cell, 4 directions, L levels deep. Pruning (mismatch at board[r][c] !== word[i]) cuts this dramatically.

13. Real Systems That Use Backtracking

Regex engines: Matching a.*b against "axxb" is backtracking. The engine tries each position where .* could end, backtracks when the match fails, and tries the next position. This is why catastrophic backtracking is a real problem — pathological regexes on pathological inputs cause O(2^n) runtime. Node.js's built-in regex engine uses backtracking; the re2 library avoids it using NFA-based matching.

SAT solvers (DPLL algorithm): Satisfiability — given boolean formula, find variable assignment that satisfies it. The DPLL algorithm is backtracking with unit propagation as pruning. Modern SAT solvers power chip verification, cryptography analysis, and AI planning.

SQL query optimizer: Choosing join order is a combinatorial problem. PostgreSQL uses dynamic programming for small queries, but for many-table joins it falls back to a heuristic backtracking search (GEQO — genetic query optimizer). The exhaustive search over all join orderings is backtracking.

Chess engines (minimax): Chess AI searches the game tree using backtracking (make move → search → unmake move). Alpha-beta pruning is the chess-specific backtracking optimization that prunes branches that can't affect the result.

Sudoku solvers: Place a number → recurse → if contradiction found, backtrack. Constraint propagation (like N-Queens with column/diagonal sets) makes this fast enough to solve any puzzle in milliseconds.

14. Complexity Summary Table

Vocabulary Map

Connect Forward

Chapter 11a applies the patterns from this chapter to 8 problems. Combination Sum and its variants (with duplicates, with limited reuse) are the highest-priority interview patterns.

Chapter 12 (Graphs) generalizes DFS beyond trees. A graph's DFS also uses choose/explore/unchoose (visit node, recurse on neighbors, mark unvisited). The main difference: graphs can have cycles, requiring an explicit visited set. Backtracking's DFS on a decision tree is a special case of graph DFS where the graph is a DAG with no cycles.

Chapter 13 (DP) often solves the "count" version of backtracking problems in polynomial time. "How many combinations sum to target?" is O(n×target) with DP. "What are all combinations that sum to target?" requires backtracking. Understanding both is essential — interviewers sometimes ask for one then pivot to the other.