Backtracking

Backtracking is a systematic method for exploring all possible solutions by building candidates incrementally and abandoning each partial candidate (backtracking) as soon as it is determined that it cannot lead to a valid solution. It is the foundation for solving constraint satisfaction problems.

The General Pattern

function backtrack(state, choices) {
  if (isSolution(state)) {
    recordSolution(state);
    return;
  }
  for (const choice of choices) {
    if (isValid(state, choice)) {
      makeChoice(state, choice);          // explore
      backtrack(state, nextChoices(...)); // recurse
      undoChoice(state, choice);          // backtrack
    }
  }
}

Generating All Permutations

Backtracking naturally enumerates all orderings of a set of elements.

function permutations(nums) {
  const result = [];

  function backtrack(current, remaining) {
    if (remaining.length === 0) {
      result.push([...current]);
      return;
    }
    for (let i = 0; i < remaining.length; i++) {
      current.push(remaining[i]);
      backtrack(current, remaining.filter((_, j) => j !== i));
      current.pop();                     // undo
    }
  }

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

permutations([1, 2, 3]).length; // 6

Combination Sum

Find all combinations of numbers that sum to a target. Numbers can be reused.

function combinationSum(candidates, target) {
  const result = [];

  function backtrack(start, current, remaining) {
    if (remaining === 0) { result.push([...current]); return; }
    for (let i = start; i < candidates.length; i++) {
      if (candidates[i] > remaining) break; // prune — sort candidates first
      current.push(candidates[i]);
      backtrack(i, current, remaining - candidates[i]);
      current.pop();
    }
  }

  candidates.sort((a, b) => a - b);
  backtrack(0, [], target);
  return result;
}

N-Queens

Place N queens on an N×N board so none attack each other. Classic constraint satisfaction problem.

function solveNQueens(n) {
  const cols = new Set(), diag1 = new Set(), diag2 = new Set();
  const board = Array.from({ length: n }, () => Array(n).fill('.'));
  const result = [];

  function backtrack(row) {
    if (row === n) { result.push(board.map(r => r.join(''))); return; }
    for (let col = 0; col < n; col++) {
      if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) continue;
      board[row][col] = 'Q';
      cols.add(col); diag1.add(row - col); diag2.add(row + col);
      backtrack(row + 1);
      board[row][col] = '.';
      cols.delete(col); diag1.delete(row - col); diag2.delete(row + col);
    }
  }

  backtrack(0);
  return result;
}

Pruning — The Key Optimisation

Backtracking without pruning is just brute force. The performance gain comes from detecting dead-ends early and cutting entire branches of the search tree. Always ask: what constraint can I check before recursing?

Time Complexity

Backtracking is worst-case exponential (exploring all branches), but effective pruning can reduce the actual runtime by orders of magnitude. For interview problems, state the worst case and explain your pruning strategy.