Pruning — making exponential search finish

Backtracking explores an exponential space. Pruning is what makes it usable: abandon a branch the moment it cannot produce a valid answer, and the tree collapses to a fraction of its size.

Prune early, not at the leaves

// Slow: builds every full combination, then checks the sum.
if (current.length === k) {
  if (sum(current) === target) results.push([...current]);
  return;
}

// Fast: abandons the branch as soon as it is doomed.
if (runningSum > target) return;                 // sorted, non-negative input
if (current.length === k) { ... }

Same answers, orders of magnitude fewer nodes. The rule is to test feasibility before recursing, not after returning.

N-Queens, the canonical example

Placing n queens naively is n! arrangements. Checking conflicts as you place each queen — same column, same diagonal — prunes almost everything:

function solveNQueens(n) {
  const cols = new Set();
  const diag = new Set();       // row - col
  const anti = new Set();       // row + col
  const board = [];
  let count = 0;

  const place = (row) => {
    if (row === n) { count++; return; }

    for (let col = 0; col < n; col++) {
      if (cols.has(col) || diag.has(row - col) || anti.has(row + col)) continue;

      cols.add(col); diag.add(row - col); anti.add(row + col); board.push(col);
      place(row + 1);
      board.pop(); anti.delete(row + col); diag.delete(row - col); cols.delete(col);
    }
  };

  place(0);
  return count;
}

The sets make each conflict check O(1). Without them you rescan the board every time and the constant factor eats the pruning.

Techniques that compound

• Constraint propagation. In Sudoku, fill forced cells before guessing.
• Ordering heuristics. Try the most constrained cell first — it fails fastest, which is what you want.
• Symmetry breaking. For N-Queens, only search half the first row; mirror the rest.
• Bounding. In optimisation problems, stop when the best possible completion cannot beat the current best. That is branch and bound.

Being honest about complexity

Pruning rarely changes the Big O — N-Queens is still exponential — but it changes what runs in a second versus a century. Say both in an interview: "worst case O(n!), but the diagonal constraints prune so hard that n = 12 solves instantly."