🔙 Backtracking

One-line summary: Explore all possible solutions by incrementally building candidates and abandoning ("backtracking") as soon as a constraint is violated.

---

Diagram

Concept

1. Choose — pick a candidate.
2. Explore — recurse with that choice.
3. Unchoose — undo the choice, try next.

Prune early: if current state already violates a constraint, skip the subtree.

Time: O(b^d) where b = branching factor, d = depth. Space: O(d) for the call stack.

---

Common Patterns

Subsets

function subsets(nums) {
  const result = [];
  function bt(start, curr) {
    result.push([...curr]);
    for (let i = start; i < nums.length; i++) {
      curr.push(nums[i]);
      bt(i + 1, curr);
      curr.pop();
    }
  }
  bt(0, []);
  return result;
}

Permutations

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

Constraint Satisfaction (N-Queens skeleton)

function solve(row, board, result) {
  if (row === board.length) {
    result.push(board.map((r) => r.join('')));
    return;
  }
  for (let col = 0; col < board.length; col++) {
    if (isValid(board, row, col)) {
      board[row][col] = 'Q';
      solve(row + 1, board, result);
      board[row][col] = '.'; // unchoose
    }
  }
}

---

Pitfalls

• Not spreading [...curr] before pushing to result — captures reference
• Missing pruning — O(b^d) blows up without early constraint checks
• Duplicate handling: sort input and skip duplicate values at same depth level

---

Practice Problems

Problem	Difficulty	Solution
LC 78 — Subsets	Medium
LC 46 — Permutations	Medium
LC 39 — Combination Sum	Medium
LC 22 — Generate Parentheses	Medium
LC 51 — N-Queens	Hard
LC 37 — Sudoku Solver	Hard
LC 131 — Palindrome Partitioning	Medium
LC 79 — Word Search	Medium
LC 47 — Permutations II	Medium
LC 52 — N-Queens II	Hard
LC 212 — Word Search II	Hard
LC 140 — Word Break II	Hard
LC 282 — Expression Add Operators	Hard
LC 301 — Remove Invalid Parentheses	Hard
LC 473 — Matchsticks to Square	Hard
LC 679 — 24 Game	Hard
LC 996 — Number of Squareful Arrays	Hard
CC — N-Queens Problem (NQUEENS)	Hard
CC — Sudoku Solver (SUDOKU)	Hard
CC — Graph Coloring (GRAPHCOL)	Hard
LC 90 — Subsets II	Medium
LC 40 — Combination Sum II	Medium
LC 77 — Combinations	Medium
LC 216 — Combination Sum III	Medium
LC 93 — Restore IP Addresses	Medium
LC 17 — Letter Combinations of a Phone Number	Medium
LC 526 — Beautiful Arrangement	Medium
LC 698 — Partition to K Equal Sum Subsets	Medium
LC 784 — Letter Case Permutation	Medium
LC 1079 — Letter Tile Possibilities	Medium
CC — Subset Generation (SUBGEN)	Medium
CC — Permutation Generation (PERMGEN)	Medium
CC — Combination Problems (COMBPROB)	Medium

---

Related Topics

• Recursion — backtracking is recursion with undo
• Dynamic Programming — DP memoises; backtracking explores

← Back to Home · © sparshjaswal