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;
}

Dry run: solveNQueens(4) — free masks along the path to its first solution

The table follows the branch that reaches the first solution. At row 0, free & -free of 1111 is 0001, so the loop tries column 0 first; that branch runs out of legal columns by row 3, and only after backing up does it take column 1, the one shown. From row 1 on, free is a single bit (1000, 0001, 0100): each queen is a forced move, not a choice among several. Every one of these free values costs one AND, one OR, one NOT, and one shift, regardless of how many columns are actually occupied — that constant cost per node is exactly what three Sets could not offer.

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(input, target) {
  const candidates = [...input].sort((a, b) => a - b); // sorting is what makes the break valid; the copy leaves the caller's array alone
  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(input, capacity) {
  const items = [...input].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.

Partition to K equal sum subsets: fill the buckets, number by number

Given positive integers nums and a count k, can all of nums be split into k groups with the same sum? Every number is used exactly once. Matchsticks to Square is the same problem with k = 4.

Three cheap checks come before any search, and each is a prune in disguise. The total must be divisible by k, otherwise no split exists. Each group must then sum to target = total / k. And no single number may exceed target, since it has to live in some group.

Now choose what the recursion decides. The tempting formulation is "pick a subset that sums to target, remove it, repeat". It works, but it is awkward to bound. The cleaner one flips the question: process the numbers one at a time and decide which of the k buckets each goes into. The tree has depth n and branching factor k, so kⁿ leaves in the worst case. For n = 16 and k = 4 that is over four billion, and the rest of the section is about why you will never see anything like that many.

Two prunes do the work. Overflow: a bucket whose sum would exceed target is not a choice; since all numbers are positive, a bucket that overflows can never come back down. Order: sort descending. A large number has the fewest buckets it still fits in, so it is the one most likely to fail, and failing at depth 2 prunes far more than failing at depth 14. When the last number is placed, no bucket exceeds target and the buckets sum to k × target, so every bucket equals target; no final check is needed.

function canPartitionKSubsets(nums, k) {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % k !== 0) return false;
  const target = total / k;
  const sorted = [...nums].sort((a, b) => b - a); // big numbers first: they have the fewest places to go
  if (sorted[0] > target) return false;
  const sums = new Array(k).fill(0); // sums[b] = what bucket b holds so far

  function place(i) {
    if (i === sorted.length) return true; // no bucket exceeds target and the total is k * target, so all equal target
    const tried = new Set();
    for (let b = 0; b < k; b++) {
      const s = sums[b];
      if (s + sorted[i] > target || tried.has(s)) continue; // overflow, or a twin of a bucket already tried
      tried.add(s);
      sums[b] += sorted[i];
      if (place(i + 1)) return true;
      sums[b] -= sorted[i];
    }
    return false;
  }

  return place(0);
}

Dry run: nums = [3, 3, 2, 2, 2, 2], k = 2, so target = 7

Sorted descending the numbers stay 3, 3, 2, 2, 2, 2. The state is the two bucket sums.

The failed branch in step 6 is the whole cost model: an early wrong choice (putting both 3s together) is only discovered after the numbers that could have exposed it have been placed. Sorting does not remove such branches, it makes them surface earlier.

Symmetry breaking: never explore the same subtree twice

Look again at the inner loop of the partition search. At the very start every bucket is empty, so the first number has k placements that are all the same in every way that matters: bucket 2 and bucket 3 are just names. Whatever completion works with the number in bucket 0 works equally with it in bucket 1, by swapping what the two buckets are called. The search tries all k and discovers k − 1 copies of one answer, and this repeats at every depth.

The fix needs a precise statement of when two choices are interchangeable. Here the rest of the search depends only on the multiset of bucket sums, because every remaining number can go into any bucket that has room. So two buckets with the same current sum are interchangeable: if placing the number in the first leads to no solution, placing it in the second cannot lead to one either. The tried set records the sums already attempted in this call, and a bucket whose sum is in the set is skipped. That is duplicate-bucket skipping, and it is all that "symmetry breaking" means in practice: cut the choices that lead to subtrees you have already proven equivalent.

Here is the effect, counted by instrumenting the function to tally calls. The input is [1, 3, 6, 3, 9, 3, 8, 7, 3, 3, 3, 7, 6, 6] with k = 4. The total is 68, so the target is 17, and the answer is false, which forces the search to exhaust its tree.

The two ideas multiply because they remove different waste. Sorting makes a doomed branch fail early; skipping twins stops that branch being explored once per equivalent labelling. The worst case is still exponential, so the honest claim is that the number of nodes visited dropped by roughly three orders of magnitude on this input, not that the bound improved. Other inputs show smaller or larger gains.

The same move appears wherever identical things are chosen from. In Combination Sum II and Subsets II the guard if (i > start && items[i] === items[i - 1]) continue; after sorting is symmetry breaking between equal numbers: picking either copy of a 2 leads to the same set of results. In N-Queens the board has a mirror image, so you may count only the boards whose first-row queen is in the left half and double that (for n = 8 the left half has 46 boards and the total is 92; for odd n, add the boards with the queen in the middle column once). The pattern is always: find a relabelling of the search that maps solutions to solutions, and explore one representative of each class.

Expression add operators: carry the last term so multiplication can undo it

Given a string of digits num and an integer target, return every way to put +, - or * between digits, or nothing at all (so digits join into a longer number), such that the expression equals target. For "232" and target 8 the answers are 2*3+2 and 2+3*2.

The choice at each step is clear: how many digits does the next operand take, and which operator goes in front of it? Between two digits there are four options (join, +, -, *), so a string of n digits has 4n-1 candidate expressions when none of them contains a zero; for "232" that is 16, and the search below visits exactly 16 complete expressions. There is no early prune on the value, because a later multiplication can push a small running total up or flip its sign, so this is plain exhaustive search whose entire craft is in making each node cheap and correct.

The difficulty is precedence. If you keep only the running value, then at 2+3 the value is 5, and appending *2 cannot be done by multiplying 5 by 2: the correct result is 2 + 3·2 = 8, not 10. The multiplication binds to the last term, not the whole value. So carry two numbers along: the running value and the lastTerm that was most recently added to it (negated if it was subtracted). A + n or - n adds ±n and makes ±n the new last term. A * n takes the last term back out of the value and puts the multiplied term in: value - lastTerm + lastTerm * n.

function addOperators(num, target) {
  const results = [];

  function go(pos, expr, value, lastTerm) {
    if (pos === num.length) {
      if (value === target) results.push(expr);
      return;
    }
    for (let end = pos + 1; end <= num.length; end++) {
      if (end > pos + 1 && num[pos] === "0") break; // "05" is not an operand; "0" alone is
      const text = num.slice(pos, end);
      const n = Number(text);
      if (pos === 0) {
        go(end, text, n, n); // the first operand has no operator in front of it
      } else {
        go(end, expr + "+" + text, value + n, n);
        go(end, expr + "-" + text, value - n, -n);
        go(end, expr + "*" + text, value - lastTerm + lastTerm * n, lastTerm * n); // take the last term back out, then multiply it
      }
    }
  }

  go(0, "", 0, 0);
  return results;
}

Dry run: the two accepted expressions for "232", target 8

The second row is the precedence rule in action: at *2 the code removes the 3 that +3 contributed and replaces it with 6, which is exactly what the expression means. Of the 16 leaves for "232", only these two have value 8; the others include 2+3+2 = 7, 2*3*2 = 12, 2+32 = 34 and 232 itself.

Cost: at most 4n-1 leaves, and building each result string takes O(n), so the work is O(n · 4ⁿ); the recursion is n deep. I checked the function against a brute force that enumerates every operator choice for every digit string up to length 7 over random targets (600 cases), comparing the sorted result lists.

Remove invalid parentheses: decide what to remove, then never repeat a result

Given a string of parentheses and letters, remove the fewest brackets that make it valid, and return every distinct result. For "()())()" the answers are "()()()" and "(())()"; for ")(" the only answer is the empty string.

Two ideas make the search small. First, compute the budget before searching. One left-to-right scan counts how many ( are left unmatched and how many ) have nothing to close. Those two numbers, removeOpen and removeClose, are exactly how many of each bracket must go, and they are the minimum, so the search never has to compare lengths or find "the shortest": every leaf that spends the budget exactly and ends balanced is an answer. For "()())()" the scan finds one stray ), so the budget is (0 opens, 1 close).

Second, remove from a whole run at a time. If you decide for every character "keep or remove", the string "))" gives four branches for two characters, and removing the first ) gives the same string as removing the second. Duplicates are the real danger here, and a Set hides them at the cost of generating all of them first. Instead, treat a run of equal brackets as one decision: how many of this run to remove, from 0 up to the smaller of the run length and the remaining budget. Different amounts leave different numbers of brackets, so those branches cannot build the same text.

function removeInvalidParentheses(s) {
  let removeOpen = 0;
  let removeClose = 0;
  for (const ch of s) {
    if (ch === "(") removeOpen++;
    else if (ch === ")") {
      if (removeOpen > 0) removeOpen--; // this ")" closes an earlier "("
      else removeClose++; // nothing to close: this ")" cannot be saved
    }
  }

  const results = [];

  function go(i, balance, open, close, text) {
    if (i === s.length) {
      if (balance === 0 && open === 0 && close === 0) results.push(text);
      return;
    }
    const ch = s[i];
    if (ch !== "(" && ch !== ")") {
      go(i + 1, balance, open, close, text + ch); // letters are never removed
      return;
    }
    let end = i;
    while (end < s.length && s[end] === ch) end++; // the run of equal brackets s[i..end)
    const run = end - i;
    const budget = ch === "(" ? open : close;
    for (let removed = 0; removed <= Math.min(run, budget); removed++) {
      const kept = run - removed;
      const nextBalance = ch === "(" ? balance + kept : balance - kept;
      if (nextBalance < 0) continue; // a prefix with more ")" than "(" can never be repaired by later characters
      go(
        end,
        nextBalance,
        ch === "(" ? open - removed : open,
        ch === ")" ? close - removed : close,
        text + ch.repeat(kept)
      );
    }
  }

  go(0, 0, removeOpen, removeClose, "");
  return results;
}

Dry run: s = "()())()", budget (0 opens, 1 close)

The runs are (, ), (, )), (, ). Each row is one call: the index, the balance of kept brackets, the remaining budget, and the text built so far.

The pruning condition nextBalance < 0 is sound for a reason worth stating: a prefix with more ) than ( can never be repaired by later characters: a later ( cannot match a ) that came before it, and a later ) only makes the imbalance worse. Complexity: the number of leaves is at most the number of ways to choose a removal amount from each run within the budget, which is exponential in the worst case (O(2ⁿ) is a safe bound for a string of length n), and each result costs O(n) to build.

I checked this exhaustively rather than by sampling: every string of length 0 to 10 over the three characters (, ) and a (88,573 strings), comparing against a brute force that tries every subset to keep and takes the longest valid ones. The results matched every time and no result was ever repeated. If you cannot argue that last part in the moment, wrapping the return in [...new Set(results)] costs little.

Unique paths III: a Hamiltonian-path count with a visited grid

A grid has a start square (1), an end square (2), empty squares (0) and obstacles (-1). Count the walks from start to end that step in the four directions and visit every non-obstacle square exactly once. Contrast this with the earlier Unique Paths problems, where you only count routes and a dynamic programme over the grid is enough. "Every square exactly once" is a different shape: the answer depends on which squares you have used, not just where you stand, so the grid-cell DP no longer applies and you search.

The search is the familiar one. From the current square try each of the four neighbours that is in bounds and not yet used, mark the current square as used, recurse, and un-mark. The new ingredient is the accounting that makes the end test correct. Count the walkable squares up front (start, end and empties together) and pass down how many are still unvisited, including the current one. Reaching the end square counts only if exactly one is left: the end square itself. Arriving there earlier is a dead end, not a solution, because squares remain that can no longer be reached.

function uniquePathsIII(grid) {
  const R = grid.length;
  const C = grid[0].length;
  let startR = 0;
  let startC = 0;
  let walkable = 0; // start + end + every empty square
  for (let r = 0; r < R; r++) {
    for (let c = 0; c < C; c++) {
      if (grid[r][c] === 1) {
        startR = r;
        startC = c;
      }
      if (grid[r][c] !== -1) walkable++;
    }
  }

  function walk(r, c, left) {
    if (grid[r][c] === 2) return left === 1 ? 1 : 0; // only the end square itself may remain
    const original = grid[r][c];
    grid[r][c] = -1; // visited behaves exactly like an obstacle
    let paths = 0;
    for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
      const nr = r + dr;
      const nc = c + dc;
      if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] !== -1) paths += walk(nr, nc, left - 1);
    }
    grid[r][c] = original; // un-choose
    return paths;
  }

  return walk(startR, startC, walkable);
}

Writing -1 into the visited square is the trick that removes a separate visited array: a used square must behave exactly like an obstacle, so make it one, and restore the original value on the way out. Restoring original rather than a hard-coded 0 matters for the start square, which holds 1.

Dry run: the grid [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]

Eleven squares are walkable (twelve cells, one obstacle). The search makes 95 calls to walk and finds two walks, written as (row, column):

Each walk has exactly 11 squares and ends on (2,2). Every other route that reaches (2,2) with squares unvisited returns 0 at that line, which is why the left === 1 test, not merely grid[r][c] === 2, is the correct base case.

Complexity: after the first step a walk has at most three squares to move to (it cannot step back onto the square it came from, which is marked), so the tree has at most about 4 · 3^N-1 nodes for N walkable squares, which is O(3^N). The problem statement keeps the grid small (at most 20 cells), which is the constraint hint that an exponential search is what is intended. Space is the recursion depth, O(N).

The bridge to dynamic programming is the same one this chapter keeps returning to. The future of the walk depends only on the set of visited squares and the current position. If you pass that set as a bitmask instead of writing into the grid, there are at most 2^N · N distinct states, and memoizing on them counts the same walks in O(2^N · N) time, at the price of O(2^N · N) memory. I used exactly that memoized count as the reference to check this function on 2,912 random grids (874 of them with at least one walk): the two always agreed, and the input grid was always left as it started.

Meet in the middle: when 2ⁿ is too big and 2^n/2 is not

Backtracking over subsets costs 2ⁿ. For n = 20 that is a million and everything above works. For n = 40 it is about 10¹², which no pruning rescues in general. If n ranges up to about 40 and the question is about a sum over a subset, there is a third option between brute force and a DP that needs small values: split the items into two halves, enumerate each half's subsets, and combine.

The idea, derived. Any subset of all n items is a subset of the first half joined with a subset of the second. So the sum of the whole subset is a + b, where a is one of the 2^n/2 sums of the left half and b one of the 2^n/2 sums of the right. The full search considers every pair (a, b), 2ⁿ of them. But for a fixed a you do not need to look at every b: you need the b nearest to goal - a, and if the right-hand sums are sorted, a binary search finds it in O(log) time. Total work: build two lists of 2^n/2 sums, sort one, and do 2^n/2 binary searches.

The problem: choose any subset (possibly empty) of nums so that its sum is as close as possible to goal, and return the smallest possible absolute difference.

function subsetSums(nums) {
  const sums = [0]; // the empty subset
  for (const x of nums) {
    const size = sums.length;
    for (let i = 0; i < size; i++) sums.push(sums[i] + x); // every existing subset, with and without x
  }
  return sums;
}

function minAbsDifference(nums, goal) {
  const mid = nums.length >> 1;
  const left = subsetSums(nums.slice(0, mid));
  const right = Float64Array.from(subsetSums(nums.slice(mid))).sort(); // typed arrays sort numerically
  let best = Infinity;
  for (const a of left) {
    const want = goal - a;
    let lo = 0;
    let hi = right.length;
    while (lo < hi) {
      const m = (lo + hi) >> 1;
      if (right[m] < want) lo = m + 1;
      else hi = m;
    } // lo = first right sum >= want
    if (lo < right.length) best = Math.min(best, Math.abs(a + right[lo] - goal));
    if (lo > 0) best = Math.min(best, Math.abs(a + right[lo - 1] - goal));
  }
  return best;
}

Dry run: nums = [1, 2, 3, 4], goal = 5

The halves are [1, 2] and [3, 4]. Left sums: 0, 1, 2, 3. Right sums, sorted: 0, 3, 4, 7.

The answer is 0 (for example 1 + 4, from a = 1 and b = 4). Note that each a checks two candidates, the right sum just at or above the target and the one just below it, because the closest value can be on either side.

Complexity: building each half's sums is O(2^n/2); sorting one is O(2^n/2 · n/2); the binary searches add O(2^n/2 · n/2). The total is O(2^n/2 · n) time and O(2^n/2) space. At n = 40 each half has 2²⁰ = 1,048,576 sums, a few tens of millions of basic steps in all, against about 10¹² for brute force; on 40 random values up to 10⁷ in magnitude it finished in well under a second here. The price is memory: both lists must be held at once.

The counting variant needs no sorting. To count the subsets whose sum is exactly target, put the right half's sums into a Map from sum to how many times it occurs, then for each left sum add seen.get(target - a).

function countSubsetsWithSum(nums, target) {
  const mid = nums.length >> 1;
  const left = subsetSums(nums.slice(0, mid));
  const seen = new Map();
  for (const b of subsetSums(nums.slice(mid))) seen.set(b, (seen.get(b) || 0) + 1);
  let count = 0;
  for (const a of left) count += seen.get(target - a) || 0;
  return count;
}

I checked both functions against brute force on 1,500 random arrays of up to 14 numbers with negatives allowed, comparing the closest difference and the subset count with direct enumeration of all 2ⁿ subsets.

Memoized backtracking: when the state is small, stop re-exploring it

The table of prune types above ends with a row that this chapter has only gestured at: memo / dedupe: have I already explored this exact state? Backtracking enumerates paths. If two different paths arrive at a state from which the future is identical, the second arrival repeats the first one's entire subtree. Remember the answer for a state the first time you finish it, and the exponential tree collapses to as many distinct states as there are. That is dynamic programming reached from the search side, and the test for whether it is allowed is one question: does this key contain everything the future depends on, and nothing it does not?

Can I Win: the state is the set of numbers used

Two players take turns choosing an unused integer from 1 to maxChoosable and adding it to a running total. The player who makes the total reach desiredTotal or more wins. Can the first player force a win? Plain backtracking tries every number for each player in turn. But look at what a position is: which numbers are gone. The running total is not an extra fact, because it is determined by the used set (remaining = desiredTotal - sum of used), and whose turn it is is determined by how many are used. So a bitmask of used numbers is a complete key, and there are at most 2^maxChoosable of them.

function canIWin(maxChoosable, desiredTotal) {
  if (desiredTotal <= 0) return true; // the target is already met before anyone moves
  if ((maxChoosable * (maxChoosable + 1)) / 2 < desiredTotal) return false; // even taking every number cannot reach it
  const memo = new Map(); // used-numbers mask -> can the player about to move force a win?

  function wins(used, remaining) {
    if (memo.has(used)) return memo.get(used);
    let result = false;
    for (let n = 1; n <= maxChoosable; n++) {
      const bit = 1 << (n - 1);
      if (used & bit) continue;
      if (n >= remaining || !wins(used | bit, remaining - n)) { // win now, or leave the opponent in a lost position
        result = true;
        break;
      }
    }
    memo.set(used, result);
    return result;
  }

  return wins(0, desiredTotal);
}

The recursion returns "can the player about to move win from here". A move wins immediately if n >= remaining, or if it leaves the opponent in a position the opponent cannot win; that is the entire game logic. Note the two guards before the search: a target of 0 or less is already met, and if even the sum of every number cannot reach the target, nobody can win.

Counted by instrumenting both versions. The plain version is exponential in the number of numbers; the memoized one stores at most one result per subset and, because it stops as soon as a winning move is found, usually far fewer. Time is O(2^m · m) in the worst case for m = maxChoosable, space O(2^m). The bitmask limits m to about 30 in JavaScript; the problem states m <= 20.

Word Break II: the state is the index where the next word starts

Given a string and a dictionary, return every sentence that splits the string into dictionary words. The state here is one number: the index start from which the rest of the string still has to be spelled. The set of sentences for s.slice(start) does not depend on how you got to start, so cache it by start.

function wordBreak(s, wordDict) {
  const words = new Set(wordDict);
  const longest = Math.max(0, ...wordDict.map((w) => w.length));
  const memo = new Map(); // start index -> every sentence that spells s.slice(start)

  function sentences(start) {
    if (start === s.length) return [""]; // one way to spell nothing: the empty sentence
    if (memo.has(start)) return memo.get(start);
    const out = [];
    for (let end = start + 1; end <= Math.min(s.length, start + longest); end++) {
      const word = s.slice(start, end);
      if (!words.has(word)) continue;
      for (const rest of sentences(end)) out.push(rest === "" ? word : word + " " + rest);
    }
    memo.set(start, out); // an empty list is stored too: it records a dead end
    return out;
  }

  return sentences(0);
}

Dry run: "catsanddog" with the words cat, cats, and, sand, dog

The memo hit is the point: two different prefixes ("cat sand" and "cats and") both end at index 7, and the suffix "dog" is spelled once. On "catsandog", which cannot be split, the same table ends with 0 → [], and the empty lists stored along the way are dead ends that later calls skip instantly.

The partition problem again, with a memo instead of symmetry skipping

The bucket search earlier carries a state of (index, multiset of bucket sums), which is awkward to use as a key. A cleaner state exists. Fill the buckets one at a time: the set of numbers already used determines the sum so far, and a bucket is finished whenever that sum reaches a multiple of target. So the used-set bitmask, plus the current bucket's partial sum (sum % target, itself determined by the mask), is a complete state, and each mask need be explored at most once.

function canPartitionKSubsetsMemo(nums, k) {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % k !== 0) return false;
  const target = total / k;
  if (nums.some((x) => x > target)) return false;
  const n = nums.length;
  const full = (1 << n) - 1;
  const known = new Uint8Array(1 << n); // 0 = not computed, 1 = can finish, 2 = cannot

  function finish(used, filled) {
    if (used === full) return true;
    if (known[used]) return known[used] === 1;
    for (let i = 0; i < n; i++) {
      if (used & (1 << i) || filled + nums[i] > target) continue;
      if (finish(used | (1 << i), (filled + nums[i]) % target)) { // reaching target starts a fresh bucket at 0
        known[used] = 1;
        return true;
      }
    }
    known[used] = 2;
    return false;
  }

  return finish(0, 0);
}

This version is O(2ⁿ · n) time and O(2ⁿ) space, so it suits n up to roughly 16 to 20 where the bucket search with symmetry skipping may or may not finish. Which is faster depends on the input: the twin skip helps most when numbers or sums repeat, while the mask memo's cost depends on n and not on the values. I compared both against a plain kⁿ enumeration on 4,000 random small inputs (1,657 of which could be split), including that neither modifies nums.

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.
• The same kind of container or item appears many times (k equal buckets, duplicate numbers) → symmetry breaking: say which quantity decides the future, and try each distinct value of it once.
• "All ways to insert operators or brackets" with a count of what to remove → carry the extra state the grammar needs (the running value and the last term, the bracket balance), compute any budget with one scan first, and decide whole runs at a time to avoid duplicate results.
• "Visit every cell exactly once" on a small grid → backtracking with a count of the squares still unvisited; with at most about 20 cells the visited set can also be a bitmask, which makes it memoizable.
• Subset sums with n around 30 to 40 and large values → meet in the middle: enumerate each half, sort one, and look up the partner for every sum of the other.
• Different paths reach the same position and the answer depends only on that position → memoize on a small key, after checking that the key holds everything the future depends on.
• 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.