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.

The tree behind it

It helps to see the tree the subsets function walks. Each node is the current path; each edge adds one element with a higher index than the last:

[]
├── [1]
│   ├── [1,2]
│   │   └── [1,2,3]
│   └── [1,3]
├── [2]
│   └── [2,3]
└── [3]

Eight nodes, eight subsets — this tree records a result at every node, which is why the function pushes on entry rather than only at leaves. The order of the output above is simply a depth-first walk of this picture. Drawing the first two levels like this, before writing code, is the quickest way to check what a "choice" is and whether duplicates or missing branches will appear.

The cost follows from the tree: 2ⁿ nodes, and copying a path of up to n elements at each, so O(n · 2ⁿ) time. The recursion depth is at most n, so the extra space — apart from the output — is O(n).

Subsets without recursion

For subsets specifically there's a neat non-recursive alternative: each subset of n items corresponds to an n-bit number, where bit i says whether item i is included. Counting from 0 to 2ⁿ − 1 enumerates them all:

function subsetsBits(nums) {
  const out = [];
  for (let mask = 0; mask < 1 << nums.length; mask++) {
    out.push(nums.filter((_, i) => mask & (1 << i)));
  }
  return out;
}

It's compact and handy for small n, but it can't prune — every mask is generated — so the recursive template wins whenever constraints let you skip branches. See bit manipulation.

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.

Combination sum: when choices can repeat

Find every combination of candidates (each usable any number of times) that sums to a target. Two small changes to the subsets template:

function combinationSum(candidates, target) {
  const results = [], path = [];
  candidates.sort((a, b) => a - b);

  function backtrack(start, remaining) {
    if (remaining === 0) { results.push([...path]); return; }
    for (let i = start; i < candidates.length; i++) {
      if (candidates[i] > remaining) break;      // sorted: nothing later fits either
      path.push(candidates[i]);
      backtrack(i, remaining - candidates[i]);   // i, not i + 1: reuse allowed
      path.pop();
    }
  }

  backtrack(0, target);
  return results;
}

combinationSum([2, 3, 6, 7], 7);   // [[2, 2, 3], [7]]

Passing i instead of i + 1 lets the same candidate be chosen again; keeping start stops [3, 2, 2] appearing as a duplicate of [2, 2, 3]. Sorting first turns a continue into a break — once a candidate is too big, every later one is too — which prunes whole rows of the tree.

Duplicates in the input

With input [1, 2, 2], the plain subsets template produces [1, 2] twice — once with each 2. The fix: sort, then at each level skip a value equal to the previous one at the same level:

for (let i = start; i < nums.length; i++) {
  if (i > start && nums[i] === nums[i - 1]) continue;   // same value, same level
  path.push(nums[i]);
  backtrack(i + 1);
  path.pop();
}

The i > start condition is the subtle part. It allows the second 2 to be used after the first (giving [2, 2]), but not instead of it as the choice at the same position. The same sort-and-skip trick handles duplicate permutations and duplicate combination sums.

Word search: backtracking on a grid

Is a word present in a grid of letters, moving between adjacent cells without reusing a cell? Choose a neighbour, explore, unchoose — where "choose" means marking the cell as used:

function exist(board, word) {
  const R = board.length, C = board[0].length;

  function dfs(r, c, k) {
    if (k === word.length) return true;               // matched every letter
    if (r < 0 || c < 0 || r >= R || c >= C || board[r][c] !== word[k]) return false;

    const saved = board[r][c];
    board[r][c] = '#';                                // choose: mark used
    const found = dfs(r + 1, c, k + 1) || dfs(r - 1, c, k + 1) ||
                  dfs(r, c + 1, k + 1) || dfs(r, c - 1, k + 1);
    board[r][c] = saved;                              // unchoose: restore
    return found;
  }

  for (let r = 0; r < R; r++)
    for (let c = 0; c < C; c++)
      if (dfs(r, c, 0)) return true;
  return false;
}

Two habits show up here. The function returns a boolean and stops at the first success — the || short-circuits, so once one path matches, no other branch is explored. And the board itself is the visited set, marked and restored in place, which saves allocating one per path. Restoring before returning — even on success — keeps the board intact for the caller.

Sudoku: pruning with a heuristic

A Sudoku solver is the template with a constraint check: pick an empty cell, try each digit that doesn't conflict, recurse, undo on failure.

function solveSudoku(board) {
  const rows = [...Array(9)].map(() => new Set());
  const cols = [...Array(9)].map(() => new Set());
  const boxes = [...Array(9)].map(() => new Set());
  const box = (r, c) => Math.floor(r / 3) * 3 + Math.floor(c / 3);
  const empty = [];

  for (let r = 0; r < 9; r++)
    for (let c = 0; c < 9; c++) {
      const v = board[r][c];
      if (v === '.') empty.push([r, c]);
      else { rows[r].add(v); cols[c].add(v); boxes[box(r, c)].add(v); }
    }

  function solve(i) {
    if (i === empty.length) return true;
    const [r, c] = empty[i];
    for (const d of '123456789') {
      if (rows[r].has(d) || cols[c].has(d) || boxes[box(r, c)].has(d)) continue;
      board[r][c] = d; rows[r].add(d); cols[c].add(d); boxes[box(r, c)].add(d);
      if (solve(i + 1)) return true;
      board[r][c] = '.'; rows[r].delete(d); cols[c].delete(d); boxes[box(r, c)].delete(d);
    }
    return false;
  }
  return solve(0);
}

That solves typical puzzles quickly. For hard ones, the biggest speed-up isn't faster checks but choosing which cell to fill next: always pick the empty cell with the fewest legal digits. A cell with one option is forced; a cell with two halves the search. This "most constrained first" heuristic shrinks the tree dramatically, and it's a general rule for constraint problems: make the choice most likely to fail early.

Common mistakes

• Not copying the path when recording a result — every result ends up as the same (eventually empty) array.
• Asymmetric choose/unchoose — setting used[i] = true but forgetting to reset it, or popping without having pushed on some branch.
• Returning before restoring shared state on an early exit, leaving the board or sets corrupted for the caller.
• Pruning too late — checking validity only at the leaves instead of as each choice is made, so the search explores whole subtrees that were doomed from the first bad choice.
• Using backtracking for a count or optimum when the subproblems repeat — that's dynamic programming's job.

Practice

In order: subsets, permutations, combination sum, subsets with duplicates, palindrome partitioning, word search, N-Queens, Sudoku. For each, sketch the first two levels of the decision tree before coding — what is a "choice" at each level, and what makes a choice invalid? See also bitmask DP, for when an exponential search over subsets has overlapping subproblems.

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. The rest is spotting the constraint that lets you prune.