🧠 HOW TO THINK ABOUT BACKTRACKING (READ FIRST)

Backtracking = build a solution one choice at a time, and the moment a choice can't lead anywhere good (or a solution is complete), undo it and try the next. It is just DFS over a tree of decisions — and the whole skill is being disciplined about one thing: every choice you make, you must be able to un-make.

1. DECISION FRAMEWORK

Senior Engineer mindset: Before writing a line of code, classify the problem. Every minute spent here saves 5 minutes of wrong-direction coding.

2. UNIVERSAL BACKTRACKING TEMPLATE

// THE UNIVERSAL TEMPLATE — memorize this skeleton
function solve(input: any[]): any[][] {
  const results: any[][] = [];
  const path: any[] = [];

  function backtrack(/* state: index, remaining capacity, etc. */) {
    // BASE CASE: solution is complete
    if (/* termination condition */) {
      results.push([...path]);   // ⚠️ COPY, not reference
      return;
    }

    for (const choice of /* choices at this step */) {
      // PRUNE: skip invalid choices early
      if (/* choice is invalid */) continue;

      // CHOOSE
      path.push(choice);
      // mutate state if needed (e.g., mark visited)

      // EXPLORE
      backtrack(/* updated state */);

      // UNCHOOSE (backtrack)
      path.pop();
      // reverse state mutation
    }
  }

  backtrack(/* initial state */);
  return results;
}

The three words to tattoo on your brain: CHOOSE → EXPLORE → UNCHOOSE. Every backtracking solution is just these 3 lines in a loop. Your job in the interview is to fill in: what are the choices, when do I terminate, and where do I prune.

3. THE 5 BACKTRACKING FLAVORS

⭐ THE #1 DECISION — start index vs used[] array (memorize this — it picks your template in 5 seconds):

ORDER DOESN'T MATTER (subsets, combinations) → pass a `start` index,
  loop `for (i = start; ...)`, recurse with i+1 (or i if reuse allowed).
  This prevents [1,2] and [2,1] from both appearing.

ORDER MATTERS (permutations) → use a `used[]` boolean array,
  loop `for (i = 0; ...)`, skip if used[i].
  This lets every element appear at every position.

If you can answer "does order matter?" in 5 seconds, you've already picked the skeleton.

4. KEYWORD → PATTERN MAP

5. TEMPLATE 1: SUBSETS

5.1 Basic Subsets — LC 78 (no duplicates)

function subsets(nums: number[]): number[][] {
  const results: number[][] = [];
  const path: number[] = [];

  function backtrack(start: number): void {
    results.push([...path]);          // collect at EVERY node, not just leaves

    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);             // CHOOSE
      backtrack(i + 1);              // EXPLORE (i+1: each element used once)
      path.pop();                    // UNCHOOSE
    }
  }

  backtrack(0);
  return results;
}
// Time: O(n * 2^n)  Space: O(n) recursion depth

5.2 Subsets with Duplicates — LC 90

function subsetsWithDup(nums: number[]): number[][] {
  nums.sort((a, b) => a - b);        // MUST sort to group duplicates
  const results: number[][] = [];
  const path: number[] = [];

  function backtrack(start: number): void {
    results.push([...path]);

    for (let i = start; i < nums.length; i++) {
      // Skip duplicate at same recursion level
      if (i > start && nums[i] === nums[i - 1]) continue;

      path.push(nums[i]);
      backtrack(i + 1);
      path.pop();
    }
  }

  backtrack(0);
  return results;
}

Key rule for duplicates: if (i > start && nums[i] === nums[i-1]) continue — i > start (not i > 0) means: only skip at THIS level, not globally.

5.3 Pick / Skip Formulation (bridges to 0/1-knapsack DP)

function subsetsPickSkip(nums: number[]): number[][] {
  const results: number[][] = [];
  const path: number[] = [];

  function backtrack(i: number): void {
    if (i === nums.length) {        // leaf: one decision made per element
      results.push([...path]);
      return;
    }
    backtrack(i + 1);               // SKIP nums[i]

    path.push(nums[i]);             // TAKE nums[i]
    backtrack(i + 1);
    path.pop();
  }

  backtrack(0);
  return results;
}
// Two formulations, same answer. for-loop collects at every node;
// pick/skip collects only at leaves. Know both — interviewers probe this.

5.4 Subsets via Bitmask Iteration (no recursion, n ≤ 20)

function subsetsBitmask(nums: number[]): number[][] {
  const n = nums.length;
  const results: number[][] = [];
  for (let mask = 0; mask < (1 << n); mask++) {  // each mask = one subset
    const subset: number[] = [];
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) subset.push(nums[i]);
    }
    results.push(subset);
  }
  return results;
}
// O(n * 2^n), zero recursion. Clean when n <= 20. Mention as an alternative.

6. TEMPLATE 2: PERMUTATIONS

6.1 Basic Permutations — LC 46 (no duplicates)

function permute(nums: number[]): number[][] {
  const results: number[][] = [];
  const used = new Array(nums.length).fill(false);
  const path: number[] = [];

  function backtrack(): void {
    if (path.length === nums.length) {
      results.push([...path]);
      return;
    }

    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;         // PRUNE: already in path

      used[i] = true;                // CHOOSE
      path.push(nums[i]);
      backtrack();                   // EXPLORE
      path.pop();                    // UNCHOOSE
      used[i] = false;
    }
  }

  backtrack();
  return results;
}
// Time: O(n * n!)  Space: O(n)

6.2 Permutations with Duplicates — LC 47

function permuteUnique(nums: number[]): number[][] {
  nums.sort((a, b) => a - b);        // sort to group duplicates
  const results: number[][] = [];
  const used = new Array(nums.length).fill(false);
  const path: number[] = [];

  function backtrack(): void {
    if (path.length === nums.length) {
      results.push([...path]);
      return;
    }

    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      // Skip: same value as prev AND prev not used in this level
      // This ensures we only pick duplicates in a fixed order
      if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;

      used[i] = true;
      path.push(nums[i]);
      backtrack();
      path.pop();
      used[i] = false;
    }
  }

  backtrack();
  return results;
}

Duplicate permutation trick: i > 0 && nums[i] === nums[i-1] && !used[i-1] — ensures among identical elements they are always picked left-to-right. !used[i-1]: prev identical element was NOT chosen (already backtracked) → skip this one.

6.3 Swap-Based Permutation (space-efficient, no used[] array)

function permuteSwap(nums: number[]): number[][] {
  const results: number[][] = [];

  function backtrack(start: number): void {
    if (start === nums.length) {
      results.push([...nums]);
      return;
    }

    for (let i = start; i < nums.length; i++) {
      [nums[start], nums[i]] = [nums[i], nums[start]];   // CHOOSE (swap)
      backtrack(start + 1);                               // EXPLORE
      [nums[start], nums[i]] = [nums[i], nums[start]];   // UNCHOOSE (swap back)
    }
  }

  backtrack(0);
  return results;
}
// ⚠️  Does NOT handle duplicates cleanly — use 6.2 for that

6.4 Constrained Permutations — Android Unlock Patterns (LC 351)

function numberOfPatterns(m: number, n: number): number {
  const skip = Array.from({ length: 10 }, () => new Array(10).fill(0));   // skip[a][b] = key between a and b
  skip[1][3] = skip[3][1] = 2; skip[4][6] = skip[6][4] = 5; skip[7][9] = skip[9][7] = 8;
  skip[1][7] = skip[7][1] = 4; skip[2][8] = skip[8][2] = 5; skip[3][9] = skip[9][3] = 6;
  skip[1][9] = skip[9][1] = skip[3][7] = skip[7][3] = 5;
  const visited = new Array(10).fill(false);
  function dfs(cur: number, len: number): number {
    let count = len >= m ? 1 : 0;                        // this pattern itself is valid
    if (len === n) return count;
    visited[cur] = true;
    for (let next = 1; next <= 9; next++) {
      const mid = skip[cur][next];
      if (!visited[next] && (mid === 0 || visited[mid])) count += dfs(next, len + 1);
    }
    visited[cur] = false;                                // un-choose
    return count;
  }
  return 4 * dfs(1, 1) + 4 * dfs(2, 1) + dfs(5, 1);      // corners ×4 · edge-centres ×4 · centre ×1
}

6.5 The k-th Permutation without enumerating — LC 60

function getPermutation(n: number, k: number): string {
  const fact = [1];
  for (let i = 1; i < n; i++) fact.push(fact[i - 1] * i);     // fact[i] = i!
  const digits = Array.from({ length: n }, (_, i) => i + 1);
  k--;                                                         // zero-index FIRST
  let res = '';
  for (let i = 0; i < n; i++) {
    const f = fact[n - 1 - i];                                 // permutations per leading digit
    const idx = Math.floor(k / f);
    res += digits.splice(idx, 1)[0];                           // pick from the REMAINING digits
    k %= f;
  }
  return res;
}

7. TEMPLATE 3: COMBINATIONS

7.1 Basic Combinations — LC 77

function combine(n: number, k: number): number[][] {
  const results: number[][] = [];
  const path: number[] = [];

  function backtrack(start: number): void {
    if (path.length === k) {
      results.push([...path]);
      return;
    }

    // PRUNE: not enough elements remaining to fill k slots
    const remaining = k - path.length;
    for (let i = start; i <= n - remaining + 1; i++) {  // upper bound prune
      path.push(i);
      backtrack(i + 1);
      path.pop();
    }
  }

  backtrack(1);
  return results;
}

7.2 Combination Sum (reuse allowed) — LC 39

function combinationSum(candidates: number[], target: number): number[][] {
  candidates.sort((a, b) => a - b);   // sort enables early termination
  const results: number[][] = [];
  const path: number[] = [];

  function backtrack(start: number, remaining: number): void {
    if (remaining === 0) {
      results.push([...path]);
      return;
    }

    for (let i = start; i < candidates.length; i++) {
      if (candidates[i] > remaining) break;   // PRUNE (sorted → all remaining > target)

      path.push(candidates[i]);
      backtrack(i, remaining - candidates[i]);  // i (not i+1): same element reusable
      path.pop();
    }
  }

  backtrack(0, target);
  return results;
}
// Time: O(n^(T/M)) where T=target, M=min candidate

7.3 Combination Sum II (no reuse, duplicates in input) — LC 40

function combinationSum2(candidates: number[], target: number): number[][] {
  candidates.sort((a, b) => a - b);
  const results: number[][] = [];
  const path: number[] = [];

  function backtrack(start: number, remaining: number): void {
    if (remaining === 0) {
      results.push([...path]);
      return;
    }

    for (let i = start; i < candidates.length; i++) {
      if (candidates[i] > remaining) break;                      // PRUNE: sum exceeded
      if (i > start && candidates[i] === candidates[i - 1]) continue; // PRUNE: duplicates

      path.push(candidates[i]);
      backtrack(i + 1, remaining - candidates[i]);   // i+1: no reuse
      path.pop();
    }
  }

  backtrack(0, target);
  return results;
}

7.4 Combination Sum III (exactly k numbers, 1-9) — LC 216

function combinationSum3(k: number, n: number): number[][] {
  const results: number[][] = [];
  const path: number[] = [];

  function backtrack(start: number, remaining: number): void {
    if (path.length === k && remaining === 0) {
      results.push([...path]);
      return;
    }
    if (path.length === k || remaining <= 0) return;  // PRUNE

    for (let i = start; i <= 9; i++) {
      if (i > remaining) break;   // PRUNE: sorted 1-9
      path.push(i);
      backtrack(i + 1, remaining - i);
      path.pop();
    }
  }

  backtrack(1, n);
  return results;
}

8. TEMPLATE 4: GRID / PATH SEARCH

8.1 Word Search — LC 79

function exist(board: string[][], word: string): boolean {
  const rows = board.length, cols = board[0].length;
  const dirs = [[0,1],[0,-1],[1,0],[-1,0]];

  function backtrack(r: number, c: number, idx: number): boolean {
    if (idx === word.length) return true;       // BASE CASE: matched all chars
    if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
    if (board[r][c] !== word[idx]) return false;
    if (board[r][c] === '#') return false;      // already visited

    const temp = board[r][c];
    board[r][c] = '#';                         // CHOOSE: mark visited IN-PLACE

    for (const [dr, dc] of dirs) {
      if (backtrack(r + dr, c + dc, idx + 1)) return true;  // short-circuit
    }

    board[r][c] = temp;                        // UNCHOOSE: restore
    return false;
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (backtrack(r, c, 0)) return true;
    }
  }
  return false;
}
// Time: O(rows*cols * 3^L)  (4 dirs, but ≤3 unexplored after step 1)  Space: O(L)

8.2 Word Search II (multiple words, Trie) — LC 212

// Build a Trie, then DFS the board
// Key optimization: delete found words from Trie to avoid re-finding
interface TrieNode {
  children: Map<string, TrieNode>;
  word: string | null;
}

function findWords(board: string[][], words: string[]): string[] {
  const root: TrieNode = { children: new Map(), word: null };
  for (const w of words) {
    let node = root;
    for (const ch of w) {
      if (!node.children.has(ch)) node.children.set(ch, { children: new Map(), word: null });
      node = node.children.get(ch)!;
    }
    node.word = w;
  }

  const result: string[] = [];
  const rows = board.length, cols = board[0].length;
  const dirs = [[0,1],[0,-1],[1,0],[-1,0]];

  function dfs(r: number, c: number, node: TrieNode): void {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    const ch = board[r][c];
    if (ch === '#' || !node.children.has(ch)) return;

    const next = node.children.get(ch)!;
    if (next.word) {
      result.push(next.word);
      next.word = null;             // avoid duplicate results
    }

    board[r][c] = '#';
    for (const [dr, dc] of dirs) dfs(r + dr, c + dc, next);
    board[r][c] = ch;

    // Prune empty Trie nodes (major optimization)
    if (next.children.size === 0) node.children.delete(ch);
  }

  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      dfs(r, c, root);

  return result;
}

8.3 Find All Paths — LC 797

function allPathsSourceTarget(graph: number[][]): number[][] {
  const n = graph.length;
  const results: number[][] = [];
  const path: number[] = [0];   // start at node 0

  function backtrack(node: number): void {
    if (node === n - 1) {
      results.push([...path]);
      return;
    }
    for (const next of graph[node]) {
      path.push(next);
      backtrack(next);
      path.pop();
    }
  }

  backtrack(0);
  return results;
}
// In a DAG: no visited set needed (no cycles).
// In a general graph (cycles possible): add a visited set, mark on enter, UNMARK on exit.
//   visited.add(node); ... dfs(next); ... visited.delete(node);  ← the unmark is backtracking

8.4 Robot Room Cleaner — LC 489 (⭐ Google favorite)

// Robot API: move(): boolean, turnLeft(), turnRight(), clean()
// You do NOT get coordinates — track them yourself relative to start.
interface Robot { move(): boolean; turnLeft(): void; turnRight(): void; clean(): void; }

function cleanRoom(robot: Robot): void {
  const visited = new Set<string>();
  const dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]];  // up, right, down, left (clockwise)

  function goBack(): void {           // turn 180°, move, turn 180° back
    robot.turnRight(); robot.turnRight();
    robot.move();
    robot.turnRight(); robot.turnRight();
  }

  function backtrack(row: number, col: number, d: number): void {
    visited.add(`${row},${col}`);
    robot.clean();

    for (let i = 0; i < 4; i++) {                 // try all 4 directions
      const nd = (d + i) % 4;
      const nr = row + dirs[nd][0], nc = col + dirs[nd][1];

      if (!visited.has(`${nr},${nc}`) && robot.move()) {
        backtrack(nr, nc, nd);
        goBack();                                 // UNCHOOSE: physically return
      }
      robot.turnRight();                          // rotate to next direction
    }
  }

  backtrack(0, 0, 0);
}
// Key insight: you can't teleport — "backtracking" means physically driving back.

8.5 Unique Paths III — LC 980 (grid + must visit ALL empty cells)

function uniquePathsIII(grid: number[][]): number {
  const rows = grid.length, cols = grid[0].length;
  let empty = 0, startR = 0, startC = 0;
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 0) empty++;
      else if (grid[r][c] === 1) { startR = r; startC = c; }
    }

  let paths = 0;
  const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];

  function backtrack(r: number, c: number, remaining: number): void {
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] === -1) return;
    if (grid[r][c] === 2) {
      if (remaining === 0) paths++;     // reached end AND covered every empty cell
      return;
    }

    grid[r][c] = -1;                    // CHOOSE: mark visited
    for (const [dr, dc] of dirs) backtrack(r + dr, c + dc, remaining - 1);
    grid[r][c] = 0;                     // UNCHOOSE: restore
  }

  backtrack(startR, startC, empty + 1); // +1 counts the start cell itself
  return paths;
}

8.6 Reconstruct Itinerary — LC 332 (⚠️ NOT actually backtracking)

// LESSON: this LOOKS like backtracking but naive backtracking TLEs.
// Correct answer = Hierholzer's algorithm for an Eulerian path (use each EDGE once).
function findItinerary(tickets: string[][]): string[] {
  const graph = new Map<string, string[]>();
  for (const [from, to] of tickets) {
    if (!graph.has(from)) graph.set(from, []);
    graph.get(from)!.push(to);
  }
  for (const dests of graph.values()) dests.sort((a, b) => b.localeCompare(a)); // pop smallest

  const route: string[] = [];
  function dfs(airport: string): void {
    const dests = graph.get(airport);
    while (dests && dests.length) dfs(dests.pop()!);  // consume edges greedily
    route.push(airport);                              // post-order push
  }

  dfs('JFK');
  return route.reverse();
}
// Interview signal: recognizing "use every edge once" → Eulerian, NOT brute backtracking.

8.7 Word Squares — LC 425 (Trie prefix-map + backtracking)

// A word square reads the same across rows and down columns: square[i][j] === square[j][i].
// Place words row by row; row r must start with the known prefix (column r of placed rows).
function wordSquares(words: string[]): string[][] {
  const n = words[0].length;

  const prefixMap = new Map<string, string[]>();   // prefix → words that have it
  for (const w of words) {
    for (let i = 0; i <= w.length; i++) {
      const pre = w.slice(0, i);
      if (!prefixMap.has(pre)) prefixMap.set(pre, []);
      prefixMap.get(pre)!.push(w);
    }
  }

  const results: string[][] = [];
  const square: string[] = [];

  function backtrack(row: number): void {
    if (row === n) {
      results.push([...square]);
      return;
    }
    let prefix = '';
    for (let r = 0; r < row; r++) prefix += square[r][row];

    for (const cand of (prefixMap.get(prefix) ?? [])) {  // PRUNE: only valid prefixes
      square.push(cand);          // CHOOSE
      backtrack(row + 1);         // EXPLORE
      square.pop();               // UNCHOOSE
    }
  }

  for (const w of words) {        // any word can seed row 0
    square.push(w);
    backtrack(1);
    square.pop();
  }
  return results;
}
// The prefix-map is what bounds the branching — without it this is hopeless.

8.8 Word Ladder II — LC 126 (BFS layering + backtracking reconstruction)

// Two-phase Hard: (1) BFS level-by-level to record every parent on a shortest path,
// then (2) backtrack over those parents to emit ALL shortest paths.
function findLadders(beginWord: string, endWord: string, wordList: string[]): string[][] {
  const dict = new Set(wordList);
  const results: string[][] = [];
  if (!dict.has(endWord)) return results;

  const parents = new Map<string, string[]>();      // word → words that reach it one step earlier
  let current = new Set<string>([beginWord]);
  const visited = new Set<string>([beginWord]);
  let found = false;

  while (current.size > 0 && !found) {
    const next = new Set<string>();
    for (const word of current) {
      for (let i = 0; i < word.length; i++) {
        for (let c = 97; c <= 122; c++) {            // try 'a'..'z' at each position
          const cand = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
          if (!dict.has(cand) || visited.has(cand)) continue;
          if (!parents.has(cand)) parents.set(cand, []);
          parents.get(cand)!.push(word);             // record edge
          next.add(cand);
          if (cand === endWord) found = true;
        }
      }
    }
    for (const w of next) visited.add(w);  // mark AFTER the level → keeps all same-level parents
    current = next;
  }

  // Phase 2: backtrack from endWord up the parent links, reverse at the base.
  const path: string[] = [endWord];
  function backtrack(word: string): void {
    if (word === beginWord) {
      results.push([...path].reverse());
      return;
    }
    for (const parent of (parents.get(word) ?? [])) {
      path.push(parent);
      backtrack(parent);
      path.pop();
    }
  }

  if (found) backtrack(endWord);
  return results;
}
// Why mark visited per-level (not per-node): a word can have multiple shortest-path
// parents in the SAME layer — marking too early drops valid paths.

9. TEMPLATE 5: CONSTRAINT SATISFACTION

9.1 N-Queens — LC 51

function solveNQueens(n: number): string[][] {
  const results: string[][] = [];
  const cols = new Set<number>();
  const diag1 = new Set<number>();  // row - col (top-left to bottom-right)
  const diag2 = new Set<number>();  // row + col (top-right to bottom-left)
  const board: number[] = [];       // board[row] = col where queen is placed

  function backtrack(row: number): void {
    if (row === n) {
      results.push(board.map(col =>
        '.'.repeat(col) + 'Q' + '.'.repeat(n - col - 1)
      ));
      return;
    }

    for (let col = 0; col < n; col++) {
      if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) continue; // PRUNE

      cols.add(col); diag1.add(row - col); diag2.add(row + col);  // CHOOSE
      board.push(col);
      backtrack(row + 1);                                           // EXPLORE
      board.pop();
      cols.delete(col); diag1.delete(row - col); diag2.delete(row + col); // UNCHOOSE
    }
  }

  backtrack(0);
  return results;
}
// Time: O(n!)  Space: O(n)

9.2 N-Queens II (count only) — LC 52

function totalNQueens(n: number): number {
  let count = 0;
  const cols = new Set<number>(), diag1 = new Set<number>(), diag2 = new Set<number>();

  function backtrack(row: number): void {
    if (row === n) { count++; return; }
    for (let col = 0; col < n; col++) {
      if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) continue;
      cols.add(col); diag1.add(row - col); diag2.add(row + col);
      backtrack(row + 1);
      cols.delete(col); diag1.delete(row - col); diag2.delete(row + col);
    }
  }

  backtrack(0);
  return count;
}

9.3 Sudoku Solver — LC 37

function solveSudoku(board: string[][]): void {
  const rowUsed = Array.from({ length: 9 }, () => new Set<number>());
  const colUsed = Array.from({ length: 9 }, () => new Set<number>());
  const boxUsed = Array.from({ length: 9 }, () => new Set<number>());

  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      if (board[r][c] !== '.') {
        const val = parseInt(board[r][c]);
        const box = Math.floor(r / 3) * 3 + Math.floor(c / 3);
        rowUsed[r].add(val); colUsed[c].add(val); boxUsed[box].add(val);
      }
    }
  }

  function backtrack(): boolean {
    for (let r = 0; r < 9; r++) {
      for (let c = 0; c < 9; c++) {
        if (board[r][c] !== '.') continue;

        const box = Math.floor(r / 3) * 3 + Math.floor(c / 3);
        for (let val = 1; val <= 9; val++) {
          if (rowUsed[r].has(val) || colUsed[c].has(val) || boxUsed[box].has(val)) continue;

          // CHOOSE
          board[r][c] = String(val);
          rowUsed[r].add(val); colUsed[c].add(val); boxUsed[box].add(val);

          if (backtrack()) return true;  // EXPLORE

          // UNCHOOSE
          board[r][c] = '.';
          rowUsed[r].delete(val); colUsed[c].delete(val); boxUsed[box].delete(val);
        }
        return false;  // no valid digit for this cell → backtrack
      }
    }
    return true;  // all cells filled
  }

  backtrack();
}
// Time: O(9^m) where m = number of empty cells

9.4 N-Queens via Bitmask (⭐ SDE3 optimal — O(1) bit-ops)

function totalNQueensBitmask(n: number): number {
  let count = 0;
  const full = (1 << n) - 1;        // n low bits set = all columns occupied

  function backtrack(cols: number, diag1: number, diag2: number): void {
    if (cols === full) { count++; return; }   // every column filled → valid board

    let avail = full & ~(cols | diag1 | diag2); // 1-bits = safe columns this row
    while (avail) {
      const pos = avail & (-avail);   // isolate lowest set bit (column to try)
      avail ^= pos;                   // remove it from candidates
      // diag1 shifts left, diag2 shifts right as we descend one row
      backtrack(cols | pos, (diag1 | pos) << 1, (diag2 | pos) >> 1);
    }
  }

  backtrack(0, 0, 0);
  return count;
}
// Time: O(n!) worst case but with tiny constants. Space: O(n) stack.

10. TEMPLATE 6: STRING PARTITIONING

10.1 Palindrome Partitioning — LC 131

function partition(s: string): string[][] {
  const results: string[][] = [];
  const path: string[] = [];
  const n = s.length;

  // Precompute palindrome check with DP (O(n^2) preprocessing)
  const isPalin = Array.from({ length: n }, () => new Array(n).fill(false));
  for (let i = n - 1; i >= 0; i--) {
    for (let j = i; j < n; j++) {
      if (s[i] === s[j] && (j - i <= 2 || isPalin[i + 1][j - 1])) {
        isPalin[i][j] = true;
      }
    }
  }

  function backtrack(start: number): void {
    if (start === n) {
      results.push([...path]);
      return;
    }

    for (let end = start; end < n; end++) {
      if (!isPalin[start][end]) continue;  // PRUNE: not a palindrome

      path.push(s.slice(start, end + 1));  // CHOOSE
      backtrack(end + 1);                  // EXPLORE
      path.pop();                          // UNCHOOSE
    }
  }

  backtrack(0);
  return results;
}
// Time: O(n * 2^n)  Space: O(n^2) for isPalin table

10.2 Generate Parentheses — LC 22

function generateParenthesis(n: number): string[] {
  const results: string[] = [];
  const path: string[] = [];

  function backtrack(open: number, close: number): void {
    if (path.length === 2 * n) {
      results.push(path.join(''));
      return;
    }

    if (open < n) {                // can still add open
      path.push('(');
      backtrack(open + 1, close);
      path.pop();
    }
    if (close < open) {            // can close only if more opens exist
      path.push(')');
      backtrack(open, close + 1);
      path.pop();
    }
  }

  backtrack(0, 0);
  return results;
}
// Time: O(4^n / sqrt(n))  Catalan number

10.3 Letter Combinations — LC 17

function letterCombinations(digits: string): string[] {
  if (!digits.length) return [];
  const map: Record<string, string> = {
    '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
    '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
  };
  const results: string[] = [];
  const path: string[] = [];

  function backtrack(idx: number): void {
    if (idx === digits.length) {
      results.push(path.join(''));
      return;
    }
    for (const ch of map[digits[idx]]) {
      path.push(ch);
      backtrack(idx + 1);
      path.pop();
    }
  }

  backtrack(0);
  return results;
}

10.4 Restore IP Addresses — LC 93

function restoreIpAddresses(s: string): string[] {
  const results: string[] = [];
  const path: string[] = [];

  function backtrack(start: number): void {
    if (path.length === 4 && start === s.length) {
      results.push(path.join('.'));
      return;
    }
    if (path.length === 4 || start === s.length) return;

    for (let len = 1; len <= 3; len++) {
      if (start + len > s.length) break;
      const seg = s.slice(start, start + len);
      if (seg.length > 1 && seg[0] === '0') break;  // PRUNE: leading zero
      if (parseInt(seg) > 255) break;               // PRUNE: > 255

      path.push(seg);
      backtrack(start + len);
      path.pop();
    }
  }

  backtrack(0);
  return results;
}

10.5 Expression Add Operators — LC 282

function addOperators(num: string, target: number): string[] {
  const results: string[] = [];

  function backtrack(idx: number, expr: string, value: number, prev: number): void {
    if (idx === num.length) {
      if (value === target) results.push(expr);
      return;
    }

    for (let len = 1; len <= num.length - idx; len++) {
      const seg = num.slice(idx, idx + len);
      if (seg.length > 1 && seg[0] === '0') break;   // no leading zeros
      const cur = parseInt(seg);

      if (idx === 0) {
        backtrack(len, seg, cur, cur);                // first operand, no operator
      } else {
        backtrack(idx + len, expr + '+' + seg, value + cur, cur);
        backtrack(idx + len, expr + '-' + seg, value - cur, -cur);
        // Multiplication: undo the previous term, re-add (prev * cur)
        backtrack(idx + len, expr + '*' + seg, value - prev + prev * cur, prev * cur);
      }
    }
  }

  backtrack(0, '', 0, 0);
  return results;
}
// The "prev" trick for multiplication is a classic interview question

10.6 Remove Invalid Parentheses — LC 301 (Hard ⭐)

// Step 1: count MINIMUM removals needed (left/right surplus).
// Step 2: backtrack trying remove-or-keep for each char, only within that budget.
function removeInvalidParentheses(s: string): string[] {
  let lRem = 0, rRem = 0;
  for (const ch of s) {
    if (ch === '(') lRem++;
    else if (ch === ')') { if (lRem > 0) lRem--; else rRem++; }
  }

  const results = new Set<string>();

  function backtrack(idx: number, l: number, r: number, open: number, path: string): void {
    if (idx === s.length) {
      if (l === 0 && r === 0 && open === 0) results.add(path);
      return;
    }
    const ch = s[idx];

    // Option 1: REMOVE this char (only a paren, only if budget remains)
    if (ch === '(' && l > 0) backtrack(idx + 1, l - 1, r, open, path);
    if (ch === ')' && r > 0) backtrack(idx + 1, l, r - 1, open, path);

    // Option 2: KEEP this char
    if (ch === '(') backtrack(idx + 1, l, r, open + 1, path + ch);
    else if (ch === ')') {
      if (open > 0) backtrack(idx + 1, l, r, open - 1, path + ch);
    } else {
      backtrack(idx + 1, l, r, open, path + ch);   // letters always kept
    }
  }

  backtrack(0, lRem, rRem, 0, '');
  return [...results];
}
// Computing the removal budget first is what bounds the search → no TLE.

11. PRUNING STRATEGIES

Pruning is what separates a working backtracker from a fast one. This is where Hard LC problems are won or lost.

11.1 Pruning Code Patterns

// PATTERN A: sorted + break (most common)
candidates.sort((a, b) => a - b);
for (let i = start; i < candidates.length; i++) {
  if (candidates[i] > remaining) break;   // all further are also > remaining
}

// PATTERN B: feasibility upper bound (combination)
for (let i = start; i <= n - (k - path.length) + 1; i++) {
  // Only loop while enough elements remain to reach k
}

// PATTERN C: duplicate skip (sorted)
for (let i = start; i < arr.length; i++) {
  if (i > start && arr[i] === arr[i - 1]) continue;
}

// PATTERN D: constraint sets for O(1) validity
const rowUsed = new Set<number>();
if (!rowUsed.has(val)) {
  rowUsed.add(val);
  backtrack(row + 1);
  rowUsed.delete(val);
}

// PATTERN E: symmetry-break for bucket-fill (LC 698/473)
for (let b = 0; b < k; b++) {
  if (buckets[b] + nums[idx] > target) continue;
  buckets[b] += nums[idx];
  if (backtrack(idx + 1)) return true;
  buckets[b] -= nums[idx];
  if (buckets[b] === 0) break;   // ⭐ skip identical empty buckets
}

12. BACKTRACKING + MEMO HYBRIDS

When to memoize: If the SAME subproblem (same arguments) can be reached via MULTIPLE different paths, and the answer is always the same regardless of path taken → cache it.

12.1 Word Break II — LC 140 (Backtracking + Memo)

function wordBreak(s: string, wordDict: string[]): string[] {
  const wordSet = new Set(wordDict);
  const memo = new Map<number, string[]>();

  function backtrack(start: number): string[] {
    if (memo.has(start)) return memo.get(start)!;
    if (start === s.length) return [''];   // base: empty suffix = one valid split

    const results: string[] = [];
    for (let end = start + 1; end <= s.length; end++) {
      const word = s.slice(start, end);
      if (!wordSet.has(word)) continue;

      const suffixResults = backtrack(end);
      for (const suffix of suffixResults) {
        results.push(suffix ? word + ' ' + suffix : word);
      }
    }

    memo.set(start, results);   // MEMOIZE: same start → same results
    return results;
  }

  return backtrack(0);
}
// Without memo: O(2^n). With memo: subproblems O(n^2), each suffix list cached.

12.2 Partition to K Equal Subsets — LC 698 (bucket-fill — the expected answer)

// PRIMARY APPROACH: fill k buckets one element at a time.
// The symmetry-break pruning (skip empty buckets) is what turns TLE into AC.
function canPartitionKSubsets(nums: number[], k: number): boolean {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % k !== 0) return false;
  const target = total / k;

  nums.sort((a, b) => b - a);            // descending: place big items first (prune sooner)
  if (nums[0] > target) return false;

  const buckets = new Array(k).fill(0);

  function backtrack(idx: number): boolean {
    if (idx === nums.length) return true;  // every item placed

    for (let b = 0; b < k; b++) {
      if (buckets[b] + nums[idx] > target) continue;

      buckets[b] += nums[idx];             // CHOOSE
      if (backtrack(idx + 1)) return true; // EXPLORE
      buckets[b] -= nums[idx];             // UNCHOOSE

      // ⭐ SYMMETRY-BREAK: if this bucket was empty, all other empty buckets
      // are identical — trying them gives the same failure. Stop here.
      if (buckets[b] === 0) break;
    }
    return false;
  }

  return backtrack(0);
}
// Same template solves LC 473 (Matchsticks → k=4) and LC 1655.

Bitmask + memo variant: define dp[mask] = true if chosen subset can be split into complete buckets. The partial fill is sum(mask) % target — fully determined by mask alone. Key the memo on mask ONLY (never mask*1000+sum — that causes collisions). O(n·2^n) states.

12.3 When Memoization Does NOT Help

// LC 46 Permutations: path [1,2,_] and path [2,1,_] both need element 3 next,
// BUT the future valid completions differ per path (no overlap).
// Memoization on just `index` won't work — need full path state.
// → Pure backtracking is correct here. Don't memoize.

// MEMO TRIGGER CHECKLIST:
// ✅ Same function arguments always produce the same result?   → memoize
// ✅ Same arguments reachable via different paths?             → memoize
// ❌ Path itself influences what's "available" next?           → don't memoize
// ❌ Each recursive call explores a structurally unique path?  → don't memoize

12.4 Game search — Flip Game II (LC 294)

function canWin(s: string, memo: Map<string, boolean> = new Map()): boolean {
  const hit = memo.get(s);
  if (hit !== undefined) return hit;
  for (let i = 0; i + 1 < s.length; i++) {
    if (s[i] === '+' && s[i + 1] === '+') {
      const next = s.slice(0, i) + '--' + s.slice(i + 2);
      if (!canWin(next, memo)) { memo.set(s, true); return true; }   // found a move that leaves the opponent losing
    }
  }
  memo.set(s, false);                                                  // every move hands the opponent a win (or no moves)
  return false;
}
// Follow-up: Sprague–Grundy numbers per run of '+' solve it in O(n²).

12.5 Expression search with floats — 24 Game (LC 679)

function judgePoint24(cards: number[]): boolean {
  const EPS = 1e-6;
  function solve(a: number[]): boolean {
    if (a.length === 1) return Math.abs(a[0] - 24) < EPS;
    for (let i = 0; i < a.length; i++) {
      for (let j = i + 1; j < a.length; j++) {
        const rest = a.filter((_, k) => k !== i && k !== j);
        const x = a[i], y = a[j];
        const results = [x + y, x * y, x - y, y - x];
        if (Math.abs(y) > EPS) results.push(x / y);
        if (Math.abs(x) > EPS) results.push(y / x);
        for (const v of results) if (solve([...rest, v])) return true;
      }
    }
    return false;
  }
  return solve(cards);
}

13. COMPLEXITY ANALYSIS

13.1 The Branching Factor Model

Time = (# leaves) × (work to build each leaf)
     = (branching factor)^depth × depth

For subsets: branching=2 (include/skip), depth=n → 2^n leaves × O(n) = O(n×2^n)
For combos:  branching≈n, depth=k → C(n,k) leaves × O(k) = O(k×C(n,k))
For perms:   branching=n at depth 0, n-1 at depth 1... → n! leaves × O(n)

INTERVIEW TIP: State the tree model first, then derive complexity.
"The recursion tree has branching factor b and depth d,
 giving O(b^d) nodes with O(d) work per node → O(d × b^d)."

✅ SELF-CHECK — explain each from memory

Reading ≠ understanding. Cover the right column and answer from memory. Anything that stalls you = the section to re-read. Get these and you can start any backtracking LC medium/hard cold.

Then write these cold (no peeking): (1) subsets, (2) permutations, (3) combination sum, (4) N-Queens, (5) word search on a grid. All five start-to-finish = you own backtracking.

Backtracking Cheat Sheet | SDE2/SDE3 FAANG Edition | TypeScript