Backtracking

Explanation

Backtracking is a depth-first exploration of a decision tree. At each step, you make a choice, explore that choice recursively, and then undo the choice (backtrack) to try another option. The key optimization over brute force is pruning: if you detect that the current partial solution can't possibly lead to a valid complete solution, you abandon it immediately rather than continuing to explore its subtree. The general template is: if the current state is a complete, valid solution, record it and return; if the current state is invalid or can't lead to a solution (prune), return early; otherwise, for each possible next choice, make the choice, recurse, and undo the choice. Classic backtracking problems: N-Queens (place N queens on an N×N board so no two attack each other — for each row, try each column, prune if the queen is attacked), Sudoku solver (for each empty cell, try digits 1-9, prune if any digit violates the rules), generating all permutations of an array (for each position, try each unused element), generating all subsets, word search on a grid (DFS that marks visited cells and unmarks on backtrack), and the combination sum problem. Backtracking time complexity is typically exponential (you're exploring an exponential-sized decision tree), but effective pruning can dramatically reduce the practical running time. The Sudoku solver's decision tree has up to 9^81 leaves in theory but prunes so aggressively that it solves puzzles in milliseconds.

Code Example

// Backtracking: generate all permutations
function permutations(nums) {
  const result = [];

  function backtrack(current, remaining) {
    // Base case: complete permutation
    if (remaining.length === 0) {
      result.push([...current]);
      return;
    }

    for (let i = 0; i < remaining.length; i++) {
      // Make a choice
      current.push(remaining[i]);
      const next = remaining.filter((_, idx) => idx !== i);

      // Recurse
      backtrack(current, next);

      // Undo the choice (backtrack)
      current.pop();
    }
  }

  backtrack([], nums);
  return result;
}

console.log(permutations([1, 2, 3]));
// [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

// N-Queens pruning example (key insight)
function isValid(board, row, col) {
  for (let r = 0; r < row; r++) {
    if (board[r] === col)             return false; // same column
    if (board[r] - r === col - row)   return false; // diagonal
    if (board[r] + r === col + row)   return false; // anti-diagonal
  }
  return true;
}

Why It Matters for Engineers

Backtracking problems appear frequently in technical interviews because they test recursive thinking, state management (make/undo choices), and pruning intuition. More importantly, understanding backtracking gives you a systematic approach to any problem that asks "find all valid combinations" or "find one valid arrangement" — patterns that come up in scheduling, configuration generation, and constraint solving. Backtracking also teaches the crucial debugging skill of visualizing a decision tree: when your recursive solution produces wrong results, drawing out the states and the choices at each node reveals where the logic diverges from what you intended.