Backtracking

What is backtracking?

Backtracking is a systematic way to iterate through all possible configurations of a search space. You build a candidate solution incrementally. At each step, if the current partial solution cannot lead to a valid complete solution, you prune that branch and backtrack — undo the last choice and try the next one.

Think of it as DFS on a decision tree:

• Each node represents a partial solution (state).
• Each edge represents a choice.
• Leaf nodes are complete solutions (accept) or dead ends (reject).
• Backtracking = DFS + early pruning.

Without pruning, backtracking degenerates to brute force. Good pruning makes intractable problems solvable in practice.

The universal template

function backtrack(state: State, choices: Choice[]): void {
  if (isGoal(state)) {
    results.push(structuredClone(state))   // snapshot — state will be mutated
    return
  }

  for (const choice of choices) {
    if (!isValid(state, choice)) continue  // prune invalid branches early

    makeChoice(state, choice)              // modify state
    backtrack(state, nextChoices(state, choice))
    undoChoice(state, choice)             // restore state (the "back" in backtracking)
  }
}

The key insight: makeChoice and undoChoice must be exact inverses. After undoing, the state must be identical to what it was before the choice. Any mutation that isn’t undone is a bug.

Subsets (LC 78)

Generate all 2^n subsets of a set with no duplicates.

Decision tree: For each element, decide to include or exclude it.

nums = [1, 2, 3]

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

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

  function backtrack(start: number): void {
    results.push([...current])           // every node in the tree is a valid subset

    for (let i = start; i < nums.length; i++) {
      current.push(nums[i])              // include nums[i]
      backtrack(i + 1)                   // recurse with elements after i
      current.pop()                      // exclude nums[i] (backtrack)
    }
  }

  backtrack(0)
  return results
}
// Time: O(n × 2^n) — 2^n subsets, O(n) to copy each
// Space: O(n) recursion depth

Using start index ensures each element is considered at most once and subsets aren’t repeated in different orders.

Subsets II (LC 90) — with duplicates

When the input has duplicates, sort first, then skip duplicate choices at the same recursion level.

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

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

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

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

  backtrack(0)
  return results
}

The guard i > start (not i > 0) is critical: it only skips duplicates within the same recursive call’s loop, not across different levels of the tree. Changing it to i > 0 would incorrectly skip valid subsets.

Permutations (LC 46)

Generate all n! permutations of distinct integers.

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

  function backtrack(): void {
    if (current.length === nums.length) {
      results.push([...current])
      return
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue
      used[i] = true
      current.push(nums[i])
      backtrack()
      current.pop()
      used[i] = false
    }
  }

  backtrack()
  return results
}
// Time: O(n × n!), Space: O(n)

Unlike subsets, permutations always iterate from index 0 (not start), using used[] to prevent reuse of the same element.

Swap-based approach (avoids the 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]]   // swap into position
      backtrack(start + 1)
      [nums[start], nums[i]] = [nums[i], nums[start]]   // swap back
    }
  }

  backtrack(0)
  return results
}

Permutations II (LC 47) — with duplicates

Sort first. Skip a duplicate element at the same level if a previous identical element was NOT used (meaning we already explored that branch).

function permuteUnique(nums: number[]): number[][] {
  nums.sort((a, b) => a - b)
  const results: number[][] = []
  const used = new Array(nums.length).fill(false)
  const current: number[] = []

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

    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue
      // Skip: same value as previous AND previous was not used in current path
      // This means the previous identical element's branch was already fully explored
      if (i > 0 && nums[i] === nums[i-1] && !used[i-1]) continue

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

  backtrack()
  return results
}

Combinations (LC 77)

Choose k numbers from 1..n. Order does not matter.

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

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

    // Pruning: remaining elements must be enough to fill k slots
    const remaining = k - current.length
    for (let i = start; i <= n - remaining + 1; i++) {
      current.push(i)
      backtrack(i + 1)
      current.pop()
    }
  }

  backtrack(1)
  return results
}
// Time: O(C(n,k) × k), Space: O(k)

The upper bound n - remaining + 1 is a pruning optimization: if fewer elements remain than slots needed, no solution is possible from this branch.

Combination Sum (LC 39) — unlimited reuse

Candidates are distinct. The same number can be used unlimited times. Target is the sum.

function combinationSum(candidates: number[], target: number): number[][] {
  candidates.sort((a, b) => a - b)       // sort for pruning
  const results: number[][] = []
  const current: number[] = []

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

    for (let i = start; i < candidates.length; i++) {
      if (candidates[i] > remaining) break   // sorted: all subsequent also too large

      current.push(candidates[i])
      backtrack(i, remaining - candidates[i]) // i (not i+1): allow reuse
      current.pop()
    }
  }

  backtrack(0, target)
  return results
}

Passing i (not i + 1) to the recursive call allows reusing the same candidate. The break on candidates[i] > remaining works because the array is sorted.

Combination Sum II (LC 40) — each used once, no duplicate combos

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

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

    for (let i = start; i < candidates.length; i++) {
      if (candidates[i] > remaining) break
      if (i > start && candidates[i] === candidates[i-1]) continue  // skip duplicate

      current.push(candidates[i])
      backtrack(i + 1, remaining - candidates[i])   // i+1: each used once
      current.pop()
    }
  }

  backtrack(0, target)
  return results
}

The difference from LC 39: pass i + 1 (no reuse), and skip duplicates at the same level.

N-Queens (LC 51)

Place n queens on an n×n board such that no two queens attack each other. Queens attack along rows, columns, and diagonals.

Observation: Place exactly one queen per row. The problem reduces to choosing a column for each row.

O(1) conflict checking using three sets:

• cols — occupied columns
• diag1 — occupied diagonals (row - col is constant along a diagonal)
• diag2 — occupied anti-diagonals (row + col is constant)

function solveNQueens(n: number): string[][] {
  const results: string[][] = []
  const board: number[] = new Array(n).fill(-1)  // board[row] = col of queen
  const cols = new Set<number>()
  const diag1 = new Set<number>()                // row - col
  const diag2 = new Set<number>()                // row + col

  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

      // Place queen
      cols.add(col); diag1.add(row - col); diag2.add(row + col)
      board[row] = col
      backtrack(row + 1)

      // Remove queen
      cols.delete(col); diag1.delete(row - col); diag2.delete(row + col)
      board[row] = -1
    }
  }

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

Word Search (LC 79)

Find if a word exists in a 2D grid by traversing adjacent cells (no cell reused).

Key trick: Mark visited cells in-place (e.g., replace with #) to avoid an extra visited array. Restore after backtracking.

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

  function dfs(r: number, c: number, idx: number): boolean {
    if (idx === word.length) return true
    if (r < 0 || r >= rows || c < 0 || c >= cols) return false
    if (board[r][c] !== word[idx]) return false

    const temp = board[r][c]
    board[r][c] = '#'                    // mark visited in-place

    const found =
      dfs(r + 1, c, idx + 1) ||
      dfs(r - 1, c, idx + 1) ||
      dfs(r, c + 1, idx + 1) ||
      dfs(r, c - 1, idx + 1)

    board[r][c] = temp                   // restore (backtrack)
    return found
  }

  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      if (dfs(r, c, 0)) return true

  return false
}
// Time: O(rows × cols × 4^len), Space: O(len) call stack

Pruning optimization: Before starting DFS, check if the grid contains enough of each character in word. If the grid has fewer ‘z’s than the word requires, return false immediately.

Sudoku Solver (LC 37)

Fill a 9×9 board with digits 1-9 such that each row, column, and 3×3 box contains each digit exactly once.

function solveSudoku(board: string[][]): void {
  const rows = Array.from({ length: 9 }, () => new Set<string>())
  const cols = Array.from({ length: 9 }, () => new Set<string>())
  const boxes = Array.from({ length: 9 }, () => new Set<string>())

  function boxIdx(r: number, c: number): number {
    return Math.floor(r / 3) * 3 + Math.floor(c / 3)
  }

  // Initialize constraint sets from given digits
  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      if (board[r][c] !== '.') {
        const d = board[r][c]
        rows[r].add(d); cols[c].add(d); boxes[boxIdx(r, c)].add(d)
      }
    }
  }

  function backtrack(): boolean {
    // Find next empty cell
    for (let r = 0; r < 9; r++) {
      for (let c = 0; c < 9; c++) {
        if (board[r][c] !== '.') continue
        const bi = boxIdx(r, c)

        for (let d = 1; d <= 9; d++) {
          const digit = String(d)
          if (rows[r].has(digit) || cols[c].has(digit) || boxes[bi].has(digit)) continue

          // Place digit
          board[r][c] = digit
          rows[r].add(digit); cols[c].add(digit); boxes[bi].add(digit)

          if (backtrack()) return true   // solution found — stop

          // Remove digit (backtrack)
          board[r][c] = '.'
          rows[r].delete(digit); cols[c].delete(digit); boxes[bi].delete(digit)
        }
        return false   // no digit worked → backtrack to previous cell
      }
    }
    return true   // no empty cells left → solved
  }

  backtrack()
}

The return false after trying all digits for a cell is what triggers the actual backtracking — it signals to the previous call that this path failed.

Pruning strategies

Pruning is what separates usable backtracking from brute force:

1. Early termination: In Combination Sum, break when candidates[i] > remaining (sorted array means all subsequent candidates also fail).
2. Duplicate skipping: After sorting, skip elements at the same recursion level that equal the previous element — guarantees no duplicate results.
3. Feasibility check: Before recursing, check if a solution is still possible. N-Queens’ conflict sets do this in O(1).
4. Remaining capacity pruning: In Combinations, bound the loop at n - remaining + 1 to ensure enough elements remain.
5. Precomputation: In Sudoku and Word Search, precompute character frequencies to reject early.

Time complexity reference

Pruning reduces average-case complexity significantly below these worst-case bounds.

Common mistakes

1. Forgetting to undo the choice — if you modify state but don’t restore it, every branch inherits stale state from previous branches. The result set silently corrupts.
2. Copying state at the wrong time — always snapshot ([...current]) when you’ve found a result, not earlier. If you push a reference to current, all results will point to the final (empty) state of current.
3. Wrong duplicate-skip guard — i > start (not i > 0) for subsets/combinations. !used[i-1] for permutations with duplicates. Mixing these up produces wrong results.
4. Passing i vs i + 1 — in combination sum, i allows reuse (LC 39), i + 1 prevents reuse (LC 40). This is a one-character bug that’s hard to spot.
5. Not sorting before deduplication — the duplicate-skip trick only works when equal elements are adjacent. Without sorting, [1, 1, 2] would not deduplicate correctly.