Backtracking — The Complete Guide

                        []
                      /    \
                   [1]      []          ← choose or skip 1
                  /   \    /   \
              [1,2]  [1] [2]   []       ← choose or skip 2
              / \   / \  / \  / \
         [1,2,3] [1,2] [1,3] [1] [2,3] [2] [3] []   ← choose or skip 3

Each leaf is a valid subset. Total leaves = 2^n = 8.
Backtracking visits this tree via DFS, collecting results at leaves.

function solve(input): Result[] {
  const result: Result[] = [];

  function backtrack(current, startOrState): void {
    // 1. BASE CASE — is current a complete solution?
    if (isComplete(current)) {
      result.push(copy(current));  // always copy!
      return;
    }

    // 2. ITERATE over choices available at this step
    for (const choice of getChoices(startOrState)) {

      // 3. PRUNE — skip invalid choices early
      if (!isValid(choice, current)) continue;

      // 4. CHOOSE — make the choice
      current.add(choice);
      markUsed(choice);

      // 5. EXPLORE — recurse to the next decision
      backtrack(current, nextState);

      // 6. UNCHOOSE — undo the choice (backtrack)
      current.remove(choice);
      unmarkUsed(choice);
    }
  }

  backtrack(initialCurrent, initialState);
  return result;
}

// The 6 steps: Base → Iterate → Prune → Choose → Explore → Unchoose
// This template covers permutations, combinations, subsets,
// constraint satisfaction, and grid search problems.

function subsets(nums: number[]): number[][] {
  const result: number[][] = [];
  const current: number[] = [];

  function backtrack(start: number): void {
    // Every partial solution is a valid subset
    result.push([...current]);

    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]);       // choose
      backtrack(i + 1);            // explore (i+1 = no reuse)
      current.pop();               // unchoose
    }
  }

  backtrack(0);
  return result;
}
// Time: O(2^n × n)  Space: O(n) recursion depth
// Key: start index prevents [1,2] and [2,1] from both appearing
// Every node in the recursion tree is a valid subset (not just leaves)

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

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

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

      used[i] = true;               // choose
      current.push(nums[i]);

      backtrack();                   // explore

      current.pop();                 // unchoose
      used[i] = false;
    }
  }

  backtrack();
  return result;
}
// Time: O(n! × n)  Space: O(n)
// Key difference from subsets: no start index (any unused element
// can go at any position), but we track used elements.

function combine(n: number, k: number): number[][] {
  const result: number[][] = [];
  const current: number[] = [];

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

    // Pruning: need (k - current.length) more elements,
    // so don't start beyond n - (k - current.length) + 1
    const remaining = k - current.length;
    for (let i = start; i <= n - remaining + 1; i++) {
      current.push(i);              // choose
      backtrack(i + 1);             // explore
      current.pop();                // unchoose
    }
  }

  backtrack(1);
  return result;
}
// Time: O(C(n,k) × k)  Space: O(k)
// Key: the pruning condition (i <= n - remaining + 1) skips
// branches where there aren't enough elements left to fill k slots.

function solveNQueens(n: number): string[][] {
  const result: string[][] = [];
  const cols = new Set<number>();
  const diag1 = new Set<number>();  // row - col
  const diag2 = new Set<number>();  // row + col

  const board: string[][] = Array.from({ length: n },
    () => new Array(n).fill('.')
  );

  function backtrack(row: number): void {
    if (row === n) {
      result.push(board.map(r => r.join('')));
      return;
    }

    for (let col = 0; col < n; col++) {
      // Prune: check all constraints
      if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) {
        continue;
      }

      // Choose
      board[row][col] = 'Q';
      cols.add(col);
      diag1.add(row - col);
      diag2.add(row + col);

      // Explore
      backtrack(row + 1);

      // Unchoose
      board[row][col] = '.';
      cols.delete(col);
      diag1.delete(row - col);
      diag2.delete(row + col);
    }
  }

  backtrack(0);
  return result;
}
// Time: O(n!) roughly  Space: O(n²) for the board
// Key: three sets track column, main diagonal, and anti-diagonal
// conflicts. Checking all three is O(1) per candidate.

function subsetsWithDup(nums: number[]): number[][] {
  nums.sort((a, b) => a - b);  // Step 1: sort!
  const result: number[][] = [];
  const current: number[] = [];

  function backtrack(start: number): void {
    result.push([...current]);

    for (let i = start; i < nums.length; i++) {
      // Skip duplicates at the SAME decision level
      if (i > start && nums[i] === nums[i - 1]) continue;

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

  backtrack(0);
  return result;
}
// Key: "i > start" means we only skip if this is NOT the first
// choice at this level. The first occurrence is always allowed.
// [1, 2, 2]: we allow [1,2(first),2(second)] but skip the branch
// where we start with the second 2 at the same level as the first.

function combinationSum(candidates: number[], target: number): number[][] {
  const result: number[][] = [];
  const current: number[] = [];

  function backtrack(start: number, remaining: number): void {
    if (remaining === 0) {
      result.push([...current]);
      return;
    }
    if (remaining < 0) return;  // prune: overshot

    for (let i = start; i < candidates.length; i++) {
      current.push(candidates[i]);
      backtrack(i, remaining - candidates[i]);  // i, not i+1!
      current.pop();
    }
  }

  backtrack(0, target);
  return result;
}
// Time: depends on target and candidates — exponential in worst case
// Key: backtrack(i, ...) allows reuse. backtrack(i+1, ...) would not.
// Sorting candidates and pruning when candidates[i] > remaining
// can significantly speed this up.

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

  function backtrack(r: number, c: number, idx: number): boolean {
    if (idx === word.length) return true;  // found!

    // Prune: out of bounds, wrong char, or already visited
    if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
    if (board[r][c] !== word[idx]) return false;

    // Choose: mark as visited
    const temp = board[r][c];
    board[r][c] = '#';

    // Explore: try all 4 directions
    const found =
      backtrack(r + 1, c, idx + 1) ||
      backtrack(r - 1, c, idx + 1) ||
      backtrack(r, c + 1, idx + 1) ||
      backtrack(r, c - 1, idx + 1);

    // Unchoose: restore the cell
    board[r][c] = temp;

    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;
}
// Time: O(m × n × 4^L) where L = word length
// Key: modify the board in-place to mark visited (saves space).
// Restore it on backtrack. This is a common interview trick.

Input: [1, 2, 3]
current = [], used = {}

Call backtrack():
├── Choose 1: current=[1], used={1}
│   ├── Choose 2: current=[1,2], used={1,2}
│   │   ├── Choose 3: current=[1,2,3] → COMPLETE ✓ → result=[[1,2,3]]
│   │   └── Unchoose 3: current=[1,2]
│   ├── Unchoose 2: current=[1]
│   ├── Choose 3: current=[1,3], used={1,3}
│   │   ├── Choose 2: current=[1,3,2] → COMPLETE ✓ → result=[[1,2,3],[1,3,2]]
│   │   └── Unchoose 2: current=[1,3]
│   ├── Unchoose 3: current=[1]
├── Unchoose 1: current=[]
├── Choose 2: current=[2], used={2}
│   ├── Choose 1: current=[2,1], used={1,2}
│   │   ├── Choose 3: current=[2,1,3] → COMPLETE ✓
│   │   └── Unchoose 3
│   ├── Unchoose 1
│   ├── Choose 3: current=[2,3], used={2,3}
│   │   ├── Choose 1: current=[2,3,1] → COMPLETE ✓
│   │   └── Unchoose 1
│   ├── Unchoose 3
├── Unchoose 2: current=[]
├── Choose 3: current=[3], used={3}
│   ├── ... (similar pattern)
│   └── Produces [3,1,2] and [3,2,1]

Final result: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Total: 3! = 6 permutations

Key observations:
- Each "Choose" pushes to current and marks used
- Each "Unchoose" pops from current and unmarks used
- The used set prevents picking the same element twice
- Every leaf (complete permutation) is added to result

Board: 4×4. Place 4 queens, one per row, no conflicts.
Constraints: no two queens share a column, main diagonal, or anti-diagonal.

Row 0: Try col 0
  Q . . .     cols={0}, diag1={0}, diag2={0}
  Row 1: Try col 0 → BLOCKED (col 0 used)
         Try col 1 → BLOCKED (diag2: 0+0=0, 1+1=2 — wait, not blocked)
         Actually col 1 → diag1: 1-1=0 → BLOCKED (same main diagonal)
         Try col 2 → cols ok, diag1: 1-2=-1 ok, diag2: 1+2=3 ok ✓
  Q . . .
  . . Q .     cols={0,2}, diag1={0,-1}, diag2={0,3}
    Row 2: Try col 0 → BLOCKED (col)
           Try col 1 → diag2: 2+1=3 → BLOCKED
           Try col 2 → BLOCKED (col)
           Try col 3 → diag1: 2-3=-1 → BLOCKED
           ALL BLOCKED → backtrack to Row 1

  Row 1: Unchoose col 2. Try col 3.
  Q . . .
  . . . Q     cols={0,3}, diag1={0,-2}, diag2={0,4}
    Row 2: Try col 1 → all checks pass ✓
  Q . . .
  . . . Q
  . Q . .     cols={0,1,3}, diag1={0,-2,1}, diag2={0,4,3}
      Row 3: Try col 0 → BLOCKED (col)
             Try col 1 → BLOCKED (col)
             Try col 2 → diag1: 3-2=1 → BLOCKED
             Try col 3 → BLOCKED (col)
             ALL BLOCKED → backtrack

    Unchoose col 1. Try col 2 → diag1: 2-2=0 → BLOCKED
    ALL BLOCKED → backtrack to Row 1
  
  Unchoose col 3 → ALL options for Row 1 exhausted → backtrack to Row 0

Row 0: Unchoose col 0. Try col 1.
  . Q . .     cols={1}, diag1={-1}, diag2={1}
  Row 1: Try col 3 → ✓
  . Q . .
  . . . Q
    Row 2: Try col 0 → ✓
  . Q . .
  . . . Q
  Q . . .
      Row 3: Try col 2 → ✓ → SOLUTION FOUND! ★
  . Q . .
  . . . Q
  Q . . .
  . . Q .

This is one of two solutions for n=4.
Pruning eliminated most of the 4^4 = 256 possible placements.

Does the problem ask to GENERATE or LIST all valid solutions?
├── NO  → Probably not backtracking.
│         Need optimal value? → DP or Greedy
│         Need count only? → DP (often)
│         Need one solution? → Backtracking with early return, or DP
└── YES → Is the input size small (n ≤ 15-20)?
          ├── NO  → Backtracking may TLE. Look for DP or math shortcuts.
          └── YES → Backtracking! What type?
                    ├── All subsets?        → Template 1 (start index, collect at every node)
                    ├── All permutations?   → Template 2 (used array, collect at leaves)
                    ├── All combinations?   → Template 3 (start index + length k)
                    ├── Grid path search?   → Template: 4-dir, mark visited, restore
                    └── Constraint puzzle?  → Template 4 (check constraints before choosing)

Duplicates in input?
├── NO  → Standard template
└── YES → Sort first. Skip: if (i > start && nums[i] === nums[i-1]) continue

Can elements be reused?
├── NO  → recurse with i + 1 (or use 'used' array)
└── YES → recurse with i (same element can be chosen again)