Backtracking: Brute Force with an Undo Button

Backtracking has a scary reputation, but it's really just organized brute force: try a choice, recurse deeper, and if it doesn't work out, undo the choice and try the next one. That undo step is the whole trick. Once you see the pattern, permutations, subsets, N-Queens, and Sudoku all become the same function with different fill-in-the-blanks.

The template

Every backtracking solution is a depth-first walk over a decision tree — each level is a decision, each branch is an option:

function backtrack(state, choices) {
  if (isComplete(state)) {
    results.push(snapshot(state)); // found a valid answer
    return;
  }
  for (const choice of choices) {
    if (!isValid(choice, state)) continue; // prune early

    state.add(choice);       // 1. choose
    backtrack(state, next);  // 2. explore
    state.remove(choice);    // 3. unchoose  ← the "backtrack"
  }
}

Choose, explore, unchoose. The symmetric add/remove around the recursive call is what lets one shared, mutable state explore an exponential tree — you're reusing the same path array for every branch instead of copying it at every node.

Warm-up: all subsets

Every subset of [1, 2, 3] is the result of a series of yes/no decisions: include the 1? include the 2? include the 3?

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

  function backtrack(start) {
    results.push([...path]);          // every path is a valid subset
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);             // choose
      backtrack(i + 1);               // explore (only items after i)
      path.pop();                     // unchoose
    }
  }

  backtrack(0);
  return results; // [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]
}

Two details carry across all these problems. First, results.push([...path]) — you must copy the path, because path itself keeps mutating after you leave. Pushing path directly is the single most common backtracking bug, and it manifests as "all my results are empty arrays". Second, the start index prevents revisiting earlier elements, which is what makes these combinations (order doesn't matter) rather than permutations.

Permutations: track what's used

For permutations order does matter, so every level considers every number — minus the ones already on the path:

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

  function backtrack() {
    if (path.length === nums.length) {
      results.push([...path]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;

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

  backtrack();
  return results;
}

Note how the unchoose step restores everything the choose step touched — both used[i] and path. A backtracking bug is almost always an asymmetry between those two lines.

N-Queens: where pruning earns its keep

Place N queens on an N×N board so none attack each other. Brute force over all placements is hopeless — but backtracking places one queen per row and prunes any column or diagonal already under attack:

function solveNQueens(n) {
  const results = [];
  const cols = new Set(), diag1 = new Set(), diag2 = new Set();
  const placement = [];

  function backtrack(row) {
    if (row === n) {
      results.push([...placement]);
      return;
    }
    for (let col = 0; col < n; col++) {
      if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col))
        continue;                              // pruned: under attack

      cols.add(col); diag1.add(row - col); diag2.add(row + col);
      placement.push(col);

      backtrack(row + 1);

      cols.delete(col); diag1.delete(row - col); diag2.delete(row + col);
      placement.pop();
    }
  }

  backtrack(0);
  return results;
}

The diagonal trick is worth memorizing: every "↘" diagonal shares a constant row − col, every "↙" diagonal shares row + col, so three Sets give O(1) attack checks.

Pruning is the difference between theory and practice here. The full decision tree for 8-Queens has ~16 million leaf placements; with pruning, the search visits only about two thousand nodes. Same algorithm shape — the continue just refuses to descend into subtrees that can't possibly contain an answer.

When backtracking is the right tool

And when it isn't: if the problem asks for a count or an optimum rather than the solutions themselves, and subproblems repeat, dynamic programming will usually crush backtracking's exponential time. Ask "do I need every solution, or just the best/count?" before committing.

Complexity stays honest: subsets are O(2ⁿ), permutations O(n!), and no cleverness changes that — the output itself is that large. Pruning helps when constraints kill most branches; it can't help when you must emit every leaf.

Wrap-up

Backtracking is DFS over a decision tree with three beats: choose, explore, unchoose. Copy the path when you record a result, keep choose/unchoose perfectly symmetric, and prune as early as the constraints allow. Master the subsets and permutations templates, and most "return all valid X" problems become fill-in-the-blanks.