Backtracking

The shape: choose, explore, un-choose

Backtracking is DFS applied to a tree you build as you go — a decision tree, where each level represents one choice and each root-to-leaf path is one complete candidate answer. The "backtrack" part is the un-choose step: after exploring everything a choice leads to, you undo it before trying the next option, so the next branch starts from a clean slate.

The template every backtracking problem is built from

function backtrack(path, choices) {
  if (/* path is a complete valid answer */ false) {
    results.push([...path]); // COPY — path keeps mutating after this
    return;
  }

  for (const choice of choices) {
    if (/* choice is invalid right now */ false) continue; // pruning

    path.push(choice);          // 1. choose
    backtrack(path, nextChoices); // 2. explore
    path.pop();                  // 3. un-choose — THE step people forget
  }
}

Subsets — include or exclude, every element

function subsets(nums) {
  const results = [];
  function backtrack(start, path) {
    results.push([...path]); // every path is valid — push at every node, not just leaves
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      backtrack(i + 1, path); // i + 1, not start + 1 — never reuse an earlier index
      path.pop();
    }
  }
  backtrack(0, []);
  return results;
}

Permutations — order matters, every element used exactly once

function permute(nums) {
  const results = [];
  function backtrack(path, used) {
    if (path.length === nums.length) {
      results.push([...path]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue; // pruning: skip anything already placed
      used[i] = true;
      path.push(nums[i]);
      backtrack(path, used);
      path.pop();
      used[i] = false; // un-choose
    }
  }
  backtrack([], new Array(nums.length).fill(false));
  return results;
}

Combinations — like subsets, but with a fixed size

function combine(n, k) {
  const results = [];
  function backtrack(start, path) {
    if (path.length === k) {
      results.push([...path]);
      return;
    }
    // prune: if not enough numbers remain to reach size k, stop early
    for (let i = start; i <= n - (k - path.length) + 1; i++) {
      path.push(i);
      backtrack(i + 1, path);
      path.pop();
    }
  }
  backtrack(1, []);
  return results;
}

That early-exit condition is real pruning, not just a style choice — it cuts off branches that provably can't reach a valid answer before ever recursing into them, which is where backtracking gets its practical speed despite the worst-case complexity being exponential.

Why the complexity looks scary and that's expected

This isn't a bug to optimize away — it's inherent to "generate every valid X." What you can optimize is how much of the tree you actually visit, by pruning invalid branches as early as possible (as seen in the N-Queens example below) rather than generating a full candidate and checking it after the fact.

N-Queens — pruning is what makes it tractable

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++) {
      const d1 = row - col, d2 = row + col;
      if (cols.has(col) || diag1.has(d1) || diag2.has(d2)) continue; // prune — this column/diagonal is under attack

      cols.add(col); diag1.add(d1); diag2.add(d2);
      placement.push(col);

      backtrack(row + 1);

      cols.delete(col); diag1.delete(d1); diag2.delete(d2); // backtrack
      placement.pop();
    }
  }
  backtrack(0);
  return results;
}

Word Search — backtracking over a grid instead of an array

The same choose/explore/un-choose shape, just with "neighbors in a grid" as the branching factor instead of "remaining array elements." This combines directly with the grid-traversal ideas from the matrix chapter.

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

  function backtrack(r, c, i) {
    if (i === word.length) return true; // matched every character — done
    if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
    if (board[r][c] !== word[i]) return false;

    const temp = board[r][c];
    board[r][c] = "#"; // mark visited IN PLACE — avoids a separate visited set

    const found =
      backtrack(r + 1, c, i + 1) ||
      backtrack(r - 1, c, i + 1) ||
      backtrack(r, c + 1, i + 1) ||
      backtrack(r, c - 1, i + 1);

    board[r][c] = temp; // UN-CHOOSE — restore before trying a different path
    return found;
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (backtrack(r, c, 0)) return true;
    }
  }
  return false;
}

Combination Sum — when you're allowed to reuse an element

Unlike combine() earlier, the same number can be picked more than once. The fix is a one-character change with a real consequence: recurse with i, not i + 1.

function combinationSum(candidates, target) {
  const results = [];
  function backtrack(start, path, remaining) {
    if (remaining === 0) { results.push([...path]); return; }
    if (remaining < 0) return; // prune — overshot, no point continuing

    for (let i = start; i < candidates.length; i++) {
      path.push(candidates[i]);
      backtrack(i, path, remaining - candidates[i]); // i, not i+1 — this number can be reused
      path.pop();
    }
  }
  backtrack(0, [], target);
  return results;
}

This single index difference (i vs i + 1) is worth internalizing as its own decision point: "can this choice repeat?" is usually the very first question to answer before writing the loop — it changes one character, but changes the whole shape of the search space.

Recognizing it in an unseen problem

• "All possible," "every combination," "every way to," "generate all"
• A brute force would need to try every candidate and check validity after the fact — backtracking checks validity during construction and prunes early
• The answer is built incrementally (one element/choice at a time), and a partial answer can be judged "still possibly valid" or "already invalid"
• Grid-based "does a path exist" → Word Search shape; mark-and-restore in place instead of a separate visited set
• "Elements can be reused" → recurse with the same index, not the next one
• If it instead asks for the best single answer rather than all answers, check whether greedy or DP applies first — those are usually faster than exploring the whole tree