Advanced backtracking

What actually separates advanced backtracking from basic

The core algorithm does not change. You still choose, explore, un-choose. What changes at this level is how cheap a decision is and how early you can reject one. Every advanced backtracking problem is the same template plus one or both of these upgrades: a smarter state representation (integers and bitmasks instead of sets and arrays) and aggressive pruning (a bound, a constraint propagation step, or a shared prefix structure like a Trie that says "no word in the entire dictionary continues this way").

Both upgrades attack the same number: nodes visited. Constant-factor work per node matters, but cutting a subtree removes 2^k or k! leaves at once. Pruning wins by orders of magnitude; state representation then makes each surviving node 5-10× cheaper.

Sets are correct; integers are fast

The intermediate N-Queens solution tracked attacks with three Sets. That is O(1) per lookup amortized, but each operation hashes a number, touches a heap-allocated bucket, and may allocate. In a search that visits millions of nodes, that constant factor is the whole runtime. When the domain is small and dense — "which of these ≤32 columns are used," "which of the digits 1-9 are taken" — a single 32-bit integer replaces the set entirely.

The last two rows are the ones that change how the code reads. With sets you loop over all candidates and skip the illegal ones; with a mask you compute the legal ones as a number and loop over exactly those. And because integers are values, not references, the "un-choose" step disappears — the caller's copy was never modified in the first place.

N-Queens with bitmasks — the canonical example

Three integers replace three sets. cols has bit c set if column c is taken. The diagonals are the clever part: instead of keying by row - col and row + col, store the diagonal attacks projected onto the current row, and shift them by one as you descend. A "" diagonal moves one column right per row down, so its mask shifts left; a "/" diagonal moves one column left, so its mask shifts right.

// all N-Queens boards — O(n!) worst case, but with a tiny constant per node
function solveNQueens(n) {
  const full = (1 << n) - 1; // n low bits set: the whole board width
  const results = [], placement = [];

  function place(row, cols, diag1, diag2) {
    if (row === n) {
      results.push(placement.map(c => ".".repeat(c) + "Q" + ".".repeat(n - c - 1)));
      return;
    }

    let free = full & ~(cols | diag1 | diag2); // every safe column, computed in one step

    while (free) {
      const bit = free & -free;  // isolate the lowest set bit — the next safe column
      free ^= bit;               // consume it so the loop terminates
      const col = 31 - Math.clz32(bit); // bit -> column index, only for the output board

      placement.push(col);
      place(
        row + 1,
        cols | bit,
        ((diag1 | bit) << 1) & full, // "" attacks slide one column right next row
        (diag2 | bit) >> 1           // "/" attacks slide one column left next row
      );
      placement.pop(); // the ONLY thing left to undo — the masks were never mutated
    }
  }

  place(0, 0, 0, 0);
  return results;
}

If the question only asks how many solutions exist (N-Queens II), delete placement and Math.clz32 entirely and return a counter. The recursion then touches nothing but four integers — no arrays, no allocation, no garbage collection pressure anywhere in the hot path.

Sudoku — bitmasks plus constraint propagation

Sudoku is where the two upgrades combine. Each row, column and 3×3 box gets a 9-bit mask of digits already used, so the candidate set for any cell is one OR and one AND away. Then comes the real accelerator: most-constrained variable first (MRV). Instead of filling cells left-to-right, always recurse on the empty cell with the fewest candidates. A cell with one candidate is a forced move; a cell with zero candidates means this branch is already dead, and you learn that before spending a single guess.

// solves a 9x9 board of "1".."9" and "." in place
function solveSudoku(board) {
  const rows = new Array(9).fill(0);
  const cols = new Array(9).fill(0);
  const boxes = new Array(9).fill(0);
  const empties = [];
  const boxOf = (r, c) => ((r / 3) | 0) * 3 + ((c / 3) | 0);
  const ALL = 0x1FF; // 9 low bits set = digits 1..9

  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      if (board[r][c] === ".") { empties.push([r, c]); continue; }
      const bit = 1 << (board[r][c].charCodeAt(0) - 49); // "1" -> bit 0
      rows[r] |= bit; cols[c] |= bit; boxes[boxOf(r, c)] |= bit;
    }
  }

  const candidates = (r, c) => ALL & ~(rows[r] | cols[c] | boxes[boxOf(r, c)]);
  const popcount = (x) => { let n = 0; while (x) { x &= x - 1; n++; } return n; };

  function solve(k) {
    if (k === empties.length) return true;

    // MRV: find the most-constrained remaining cell and swap it into slot k
    let pick = k, fewest = 10;
    for (let i = k; i < empties.length; i++) {
      const cnt = popcount(candidates(empties[i][0], empties[i][1]));
      if (cnt < fewest) { fewest = cnt; pick = i; if (cnt <= 1) break; }
    }
    if (fewest === 0) return false; // a cell with no legal digit — dead branch, prune now

    const swap = empties[k]; empties[k] = empties[pick]; empties[pick] = swap;
    const [r, c] = empties[k], b = boxOf(r, c);

    let free = candidates(r, c);
    while (free) {
      const bit = free & -free;
      free ^= bit;

      rows[r] |= bit; cols[c] |= bit; boxes[b] |= bit;
      board[r][c] = String.fromCharCode(49 + (31 - Math.clz32(bit)));

      if (solve(k + 1)) return true;

      rows[r] ^= bit; cols[c] ^= bit; boxes[b] ^= bit; // un-choose: XOR clears the bit we set
      board[r][c] = ".";
    }

    empties[pick] = empties[k]; empties[k] = swap; // restore the ordering before failing upward
    return false;
  }

  solve(0);
  return board;
}

The swap-into-slot-k trick keeps the "remaining cells" set implicit — indices k..end are unfilled, 0..k-1 are done — so MRV costs a linear scan of the remainder instead of a heap, and reordering needs no extra structure. Restoring the swap on the failure path is what keeps the invariant true for the caller.

Real constraint propagation goes one step further than MRV: after placing a digit, repeatedly scan for any cell that now has exactly one candidate and place it too, with no branching at all, until nothing more is forced. Most "hard" published Sudokus solve almost entirely by propagation with a handful of guesses. You will not usually be asked to implement it, but naming it — "this is MRV plus unit propagation, the same idea a SAT solver uses" — is a strong signal.

Word Search II — a Trie prunes the whole dictionary at once

The naive extension of Word Search is to run the single-word grid search once per word: O(W · R · C · 4^L). That re-walks the same board prefixes for every word sharing them. The fix is to invert the loop — walk the board once and carry a Trie node (see the Tries chapter) alongside the position. The moment the current cell's letter has no child in the Trie, no word in the entire dictionary continues this way, and the branch dies immediately.

function findWords(board, words) {
  const root = {};
  for (const w of words) { // build the Trie: shared prefixes are shared work
    let node = root;
    for (const ch of w) node = node[ch] || (node[ch] = {});
    node.word = w; // terminal marker that also carries the answer string
  }

  const R = board.length, C = board[0].length, found = [];

  function dfs(r, c, parent) {
    const ch = board[r][c];
    const node = parent[ch];
    if (!node) return; // THE prune: no dictionary word continues with this letter

    if (node.word) { found.push(node.word); delete node.word; } // delete = dedupe, no Set needed

    board[r][c] = "#"; // "#" is never a Trie key, so revisits prune on the line above
    if (r > 0)     dfs(r - 1, c, node);
    if (r + 1 < R) dfs(r + 1, c, node);
    if (c > 0)     dfs(r, c - 1, node);
    if (c + 1 < C) dfs(r, c + 1, node);
    board[r][c] = ch; // un-choose

    if (Object.keys(node).length === 0) delete parent[ch]; // trim exhausted branches for good
  }

  for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) dfs(r, c, root);
  return found;
}

Three separate prunes are stacked here and each is worth naming out loud: (1) missing child kills a branch in O(1); (2) delete node.word after a hit means a duplicate is never reported and no Set is needed; (3) deleting a Trie node once its subtree is empty shrinks the dictionary permanently, so later starting cells search a strictly smaller structure. Complexity drops from O(W · R · C · 4^L) to O(R · C · 4^L) with L now bounded by the longest word, and in practice far below that because the Trie kills most branches at depth 2-3.

Branch and bound — pruning with a number, not just a rule

Everything above prunes on feasibility: this branch cannot produce a valid answer. Branch and bound prunes on optimality: this branch cannot produce a better answer than one already found. You need three ingredients — the best answer so far, an optimistic bound on what the current branch could still reach, and the comparison between them.

The simplest form is the one already hiding in Combination Sum. Sort the candidates and break instead of continue:

function combinationSum(candidates, target) {
  candidates.sort((a, b) => a - b); // sorting is what makes the break valid
  const results = [], path = [];

  function go(start, remaining) {
    if (remaining === 0) { results.push([...path]); return; }

    for (let i = start; i < candidates.length; i++) {
      if (candidates[i] > remaining) break; // sorted ⇒ every LATER candidate also overshoots
      path.push(candidates[i]);
      go(i, remaining - candidates[i]);
      path.pop();
    }
  }

  go(0, target);
  return results;
}

continue would still be correct and would still terminate — it just wastes the rest of the loop testing values that are provably too large. Turning a continue into a break by first establishing an ordering is the smallest, most repeatable pruning upgrade there is, and it applies to Combination Sum II, Palindrome Partitioning and most "sum to target" variants unchanged.

The general version needs a real bound function. For 0/1 knapsack, the classic optimistic estimate is the fractional relaxation: sort items by value density and pretend you may take a fraction of the item that straddles the capacity limit. That is never worse than the true optimum, so if even it cannot beat the incumbent, the whole subtree is dead.

// 0/1 knapsack by branch and bound — exponential worst case, near-instant in practice
function knapsack(items, capacity) {
  items.sort((a, b) => b.value / b.weight - a.value / a.weight); // densest first
  const n = items.length;
  let best = 0;

  // optimistic: allow a fractional last item, so bound >= any real completion
  function bound(i, room, taken) {
    let estimate = taken, left = room;
    for (let j = i; j < n && left > 0; j++) {
      const take = Math.min(items[j].weight, left);
      estimate += items[j].value * (take / items[j].weight);
      left -= take;
    }
    return estimate;
  }

  function go(i, room, taken) {
    if (i === n) { best = Math.max(best, taken); return; }
    if (bound(i, room, taken) <= best) return; // THE bound: cannot beat the incumbent

    // take first: densest-first ordering raises `best` fast, which strengthens every later bound
    if (items[i].weight <= room) go(i + 1, room - items[i].weight, taken + items[i].value);
    go(i + 1, room, taken);
  }

  go(0, capacity, 0);
  return best;
}

The fourth row is the boundary where backtracking turns into DP. If the state reaching a node is fully described by a small key (a bitmask of used elements, an index plus a remainder), memoize it and the exponential tree collapses to a polynomial-in-2^n table — that is exactly the bridge into the bitmask-DP section of the Advanced DP chapter.

Ordering the search is free speed

Two branches, same subtree size, different order of exploration — the runtimes can differ by 100×. Bound-based pruning only works once best is good, so anything that finds a good answer sooner strengthens every subsequent prune. Three heuristics carry most of the value:

• Most-constrained variable first — branch on the cell/slot with the fewest options (Sudoku MRV). Fewer children means failure surfaces at a shallower depth.
• Least-constraining value first — among the options for that slot, try the one that eliminates the fewest options elsewhere, so a solution is reached before the search has to unwind.
• Greedy-first ordering — sort by value density (knapsack), largest item first (bin packing, Partition to K Equal Sum Subsets), so the incumbent jumps early. Largest-first also fails fast: if the biggest item fits nowhere, you learn it at depth 1 instead of depth n.

Complexity at this level: say the honest thing

Notice that the worst-case column barely moves. Saying "pruning makes this O(n log n)" is wrong and interviewers catch it instantly. The correct framing is: the worst case is unchanged, the expected number of visited nodes collapses, and here is the specific reason a branch dies. Being precise about that distinction reads as senior; over-claiming reads as memorized.

Recognizing it in an unseen problem

• Basic backtracking is already the obvious approach, but n or the branching factor makes the plain version time out — the question is not "which algorithm" but "which prune."
• The state is a small dense set (≤ 30 columns, 9 digits, ≤ 20 items used) → replace sets/arrays with a bitmask; full & ~(a|b|c) and x & -x are the two idioms to reach for.
• Many candidate strings/words are searched against one structure → build a Trie and invert the loops: walk the structure once carrying a Trie node, instead of once per word.
• The problem asks for the best value rather than all answers → you now have an incumbent, so branch and bound applies; find an optimistic bound (relaxation: drop the integrality constraint, ignore capacity, allow fractions) and prune when bound ≤ best.
• Candidates can be sorted so failure is monotone → change continue to break; free, and it composes with everything else.
• Distinguish from DP: if two different paths reach the same state and the future depends only on that state, memoize and it becomes bitmask DP. Backtracking is the right tool when states are mostly distinct or you must enumerate rather than count.