Backtracking: The Art of Exploring All Possibilities

What is Backtracking?

Backtracking is a systematic way to explore all possible solutions by building candidates incrementally and abandoning a candidate (“backtracking”) as soon as you determine it cannot lead to a valid solution. Think of it as navigating a maze: you explore a path, and if you hit a dead end, you go back and try a different path.

The core idea follows a try-fail-undo pattern:

1. Make a choice - Pick an option from available candidates
2. Explore - Recursively explore with that choice
3. Undo the choice - Remove the choice and try the next option

This approach naturally forms a decision tree where each node represents a state, and branches represent choices. Backtracking explores this tree using depth-first search, pruning branches that cannot lead to valid solutions.

When to Use Backtracking

Backtracking is your go-to technique when:

• Generating all permutations - All orderings of elements (n! results)
• Generating all combinations - Selecting k items from n (C(n,k) results)
• Generating all subsets - Power set, all possible selections (2^n results)
• Constraint satisfaction - N-Queens, Sudoku, graph coloring
• Path finding with conditions - Word search, maze solving
• Partitioning problems - Splitting elements into groups meeting criteria

Key signal: If the problem asks for “all possible” solutions or involves making sequential choices where each choice affects future options, backtracking is likely the answer.

The Universal Backtracking Template

Nearly every backtracking problem follows this same structure. Memorize this template and adapt it to specific problems:

function backtrack(
  currentState: State,
  choices: Choice[],
  results: Result[]
): void {
  // Base case: found a valid solution
  if (isComplete(currentState)) {
    results.push(currentState.copy())
    return
  }

  // Try each available choice
  for (const choice of choices) {
    // Pruning: skip invalid choices early
    if (!isValid(choice, currentState)) {
      continue
    }

    // 1. Make the choice
    currentState.add(choice)

    // 2. Explore further with this choice
    backtrack(currentState, getNextChoices(choice), results)

    // 3. Undo the choice (backtrack)
    currentState.remove(choice)
  }
}

The three critical steps happen in the loop: make choice,explore, undo choice. The undo step is what gives backtracking its name - you are literally tracking back to try other options.

Problem 1: Subsets (Power Set)

Question: Given an array of unique integers, return all possible subsets.

Approach: For each element, we have two choices: include it or exclude it. This creates a binary decision tree with 2^n leaves.

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

  function backtrack(start: number, current: number[]): void {
    // Every node is a valid subset, add it
    results.push([...current])

    // Try adding each remaining element
    for (let i = start; i < nums.length; i++) {
      // Make choice: include nums[i]
      current.push(nums[i])

      // Explore: only consider elements after i (avoid duplicates)
      backtrack(i + 1, current)

      // Undo choice
      current.pop()
    }
  }

  backtrack(0, [])
  return results
}

// Example: subsets([1, 2, 3])
// Output: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

Key insight: We use start to ensure we only pick elements after our current position. This prevents duplicates like [1,2] and [2,1].

Problem 2: Permutations

Question: Given an array of unique integers, return all possible orderings.

Approach: Unlike subsets, order matters here. We need to track which elements we have already used in the current permutation.

function permute(nums: number[]): number[][] {
  const results: number[][] = []
  const used = new Set<number>()

  function backtrack(current: number[]): void {
    // Base case: permutation complete
    if (current.length === nums.length) {
      results.push([...current])
      return
    }

    // Try each unused element
    for (let i = 0; i < nums.length; i++) {
      if (used.has(i)) continue  // Skip already used

      // Make choice
      current.push(nums[i])
      used.add(i)

      // Explore
      backtrack(current)

      // Undo choice
      current.pop()
      used.delete(i)
    }
  }

  backtrack([])
  return results
}

// Example: permute([1, 2, 3])
// Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Key insight: For permutations, we can pick ANY unused element at each step (not just elements after our position). The used set tracks what is already in our current permutation.

Problem 3: Combination Sum

Question: Find all unique combinations of candidates that sum to target. Each number can be used unlimited times.

Approach: Similar to subsets, but we can reuse elements. We prune when the sum exceeds target.

function combinationSum(
  candidates: number[],
  target: number
): number[][] {
  const results: number[][] = []

  function backtrack(
    start: number,
    current: number[],
    remaining: number
  ): void {
    // Base case: found valid combination
    if (remaining === 0) {
      results.push([...current])
      return
    }

    // Pruning: can't reach target
    if (remaining < 0) {
      return
    }

    // Try each candidate from start position
    for (let i = start; i < candidates.length; i++) {
      // Make choice
      current.push(candidates[i])

      // Explore: pass i (not i+1) to allow reuse
      backtrack(i, current, remaining - candidates[i])

      // Undo choice
      current.pop()
    }
  }

  backtrack(0, [], target)
  return results
}

// Example: combinationSum([2, 3, 6, 7], 7)
// Output: [[2,2,3], [7]]

Key insight: When we can reuse elements, we pass i instead of i + 1 to the recursive call. Pruning with remaining < 0prevents exploring impossible branches.

Problem 4: N-Queens

Question: Place N queens on an NxN chessboard so no two queens attack each other. Return all distinct solutions.

Approach: Place queens row by row. For each row, try each column. A queen is safe if no other queen shares its column or diagonals.

function solveNQueens(n: number): string[][] {
  const results: string[][] = []
  const board: string[][] = Array(n).fill(null)
    .map(() => Array(n).fill('.'))

  // Track attacked columns and diagonals
  const cols = new Set<number>()
  const diag1 = new Set<number>()  // row - col
  const diag2 = new Set<number>()  // row + col

  function isSafe(row: number, col: number): boolean {
    return !cols.has(col) &&
           !diag1.has(row - col) &&
           !diag2.has(row + col)
  }

  function backtrack(row: number): void {
    // Base case: all queens placed
    if (row === n) {
      results.push(board.map(r => r.join('')))
      return
    }

    // Try each column in current row
    for (let col = 0; col < n; col++) {
      if (!isSafe(row, col)) continue

      // Make choice: place queen
      board[row][col] = 'Q'
      cols.add(col)
      diag1.add(row - col)
      diag2.add(row + col)

      // Explore next row
      backtrack(row + 1)

      // Undo choice: remove queen
      board[row][col] = '.'
      cols.delete(col)
      diag1.delete(row - col)
      diag2.delete(row + col)
    }
  }

  backtrack(0)
  return results
}

// Example: solveNQueens(4)
// Output: [[".Q..","...Q","Q...","..Q."],
//          ["..Q.","Q...","...Q",".Q.."]]

Key insight: Queens on the same diagonal satisfy eitherrow - col = constant (one diagonal direction) orrow + col = constant (other diagonal). Using sets makes checking safety O(1).

Problem 5: Word Search

Question: Given a 2D grid of letters and a word, determine if the word exists in the grid. You can move up, down, left, or right to adjacent cells.

Approach: Start from each cell that matches the first letter. Use backtracking to explore all four directions, marking visited cells.

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

  function backtrack(
    row: number,
    col: number,
    index: number
  ): boolean {
    // Base case: found complete word
    if (index === word.length) {
      return true
    }

    // Bounds check and character match
    if (row < 0 || row >= rows ||
        col < 0 || col >= cols ||
        board[row][col] !== word[index]) {
      return false
    }

    // Make choice: mark as visited
    const temp = board[row][col]
    board[row][col] = '#'

    // Explore all four directions
    const found =
      backtrack(row + 1, col, index + 1) ||
      backtrack(row - 1, col, index + 1) ||
      backtrack(row, col + 1, index + 1) ||
      backtrack(row, col - 1, index + 1)

    // Undo choice: restore cell
    board[row][col] = temp

    return found
  }

  // Try starting from each cell
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (backtrack(r, c, 0)) {
        return true
      }
    }
  }

  return false
}

// Example: board = [["A","B"],["C","D"]], word = "ABCD" → true

Key insight: We temporarily modify the board to mark visited cells (using '#'), then restore it during backtracking. This is more efficient than maintaining a separate visited set.

Time Complexity Analysis

Backtracking problems typically have exponential time complexity because we are exploring a decision tree. However, pruning significantly reduces the actual runtime.

Why pruning matters: Without pruning, N-Queens would be O(n^n) (try all positions). With column and diagonal constraints, it is reduced to roughly O(n!). Good pruning can make the difference between TLE and accepted.

Space Complexity

Space complexity is typically O(n) or O(solution size):

• Recursion stack: O(depth) where depth is max choices
• Current state: O(n) for storing current path/permutation
• Results: Can be exponential if storing all solutions

Common Mistakes to Avoid

• Forgetting to undo: Always restore state after the recursive call. Missing pop() or delete() leads to corrupted results.
• Wrong loop bounds: For combinations, start from current index. For permutations, iterate all and check used.
• Shallow copy trap: Use [...current] or current.slice()when adding to results, not the reference itself.
• Missing base case: Know when a solution is complete and add it to results.
• Inefficient pruning: Check validity before making a choice, not after.

Pro Tips for Interviews

• Identify the decision tree: Draw 2-3 levels to understand the structure
• State your pruning conditions: Explain how you avoid invalid paths
• Start with the template: Base case, loop through choices, make-explore-undo
• Clarify duplicates: Ask if input has duplicates and if results should be unique
• Trace through an example: Walk through a small input to verify correctness

Practice Problems

Solidify your understanding with these progressively harder problems:

• Easy: Letter Case Permutation, Binary Watch
• Medium: Subsets II (with duplicates), Combination Sum II, Palindrome Partitioning
• Hard: Sudoku Solver, Expression Add Operators, Word Ladder II

Continue Learning

• Dynamic Programming Guide - When overlapping subproblems make backtracking inefficient
• Graph Algorithms - DFS and BFS traversal patterns
• Tree Traversals - Recursive patterns that apply to backtracking
• Big O Notation Explained - Understanding exponential complexity
• Start Practicing - Apply backtracking to real interview problems