Recursion & Backtracking

Definition

Recursion solves a problem by having a function call itself on a smaller version of the same problem, with a base case that stops the recursion once the problem is small enough to answer directly. Backtracking builds on recursion to search through a space of choices: at each step it picks one option, recurses to explore the consequences of that choice, and if the recursive call reaches a dead end, a state that cannot possibly lead to a valid solution, it undoes the choice and tries the next option instead. That undo step, often as simple as popping the last choice off an array or clearing a visited flag, is what separates backtracking from plain recursion: without it, the state from an abandoned branch would leak into the sibling branches tried afterward. Because each call frame captures the state made at that decision point, the call stack naturally tracks the sequence of choices made so far and unwinds it automatically when a function returns, so returning from a recursive call is often exactly the undo step a backtracking algorithm needs. Backtracking is used to enumerate or search a solution space that is too large to check exhaustively in advance, such as all permutations of a list, all ways to place non-attacking queens on a board, or all paths through a maze, and it prunes branches early whenever it can prove a partial choice cannot possibly succeed, which avoids wasting time exploring the rest of a doomed branch.

Examples

function subsets(nums) {
  const result = [];
  function backtrack(start, current) {
    result.push([...current]);
    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]);
      backtrack(i + 1, current);
      current.pop(); // undo the choice
    }
  }
  backtrack(0, []);
  return result;
}
subsets([1, 2]); // [[], [1], [1, 2], [2]]

function permute(nums) {
  const result = [], used = new Set();
  function backtrack(path) {
    if (path.length === nums.length) { result.push([...path]); return; }
    for (const n of nums) {
      if (used.has(n)) continue;
      used.add(n);
      path.push(n);
      backtrack(path);
      path.pop();
      used.delete(n); // undo before trying the next candidate
    }
  }
  backtrack([]);
  return result;
}
permute([1, 2, 3]).length; // 6

function hasPath(grid, r, c, visited = new Set()) {
  const key = `${r},${c}`;
  if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length) return false;
  if (grid[r][c] === 1 || visited.has(key)) return false; // dead end
  if (r === grid.length - 1 && c === grid[0].length - 1) return true;
  visited.add(key);
  const found = hasPath(grid, r + 1, c, visited) || hasPath(grid, r, c + 1, visited);
  visited.delete(key); // backtrack so other paths can revisit this cell
  return found;
}

Key takeaways

• Backtracking is recursion plus an explicit undo step for whichever choice was just tried.
• A dead end should stop the current branch immediately and trigger backtracking, not continue exploring further.
• The call stack unwinding on return often performs the undo automatically, but any state mutated outside the call, like an array or set, must be undone manually.
• Pruning a branch as soon as it can be proven invalid avoids wasted work exploring the rest of it.

Where you see this

• Generating all permutations, subsets, or combinations of a set of items.
• Solving constraint satisfaction puzzles such as Sudoku or the N-Queens problem.
• Searching a maze or grid for a path, undoing a step whenever it leads to a dead end.
• Parsing or compiling, where a parser tries one grammar rule, backs out if it fails, and tries another.