• When to Use Backtracking
• Backtracking Template & Pruning
• Classic Problems
• Branch-and-Bound (B&B)
• Designing Bounds
• Exercises

Backtracking systematically searches a solution space by building candidates incrementally and abandoning a branch as soon as it is determined to be invalid or suboptimal.

• Use cases: permutations/combinations, constraint satisfaction (N-Queens, Sudoku), subset search.
• Key: pruning by feasibility checks or dominance rules to reduce the search tree.
• Complexity: worst case exponential; practical performance hinges on pruning quality.

// Generic backtracking with pruning
function backtrack(path, choices) {
  if (isSolution(path)) { record(path); return; }
  for (const choice of choicesFor(path, choices)) {
    if (!feasible(path, choice)) continue; // prune infeasible
    apply(path, choice);
    backtrack(path, choices);
    undo(path, choice);
  }
}

• Order choices: heuristic ordering (MRV, degree) can drastically cut branches.
• Early stopping: stop when first/optimal solution is found as needed.
• Memoization: sometimes applicable to avoid revisiting equivalent states.

// N-Queens: count solutions
function totalNQueens(n) {
  let count = 0;
  const cols = new Set(), diag1 = new Set(), diag2 = new Set();
  function dfs(r) {
    if (r === n) { count++; return; }
    for (let c = 0; c < n; c++) {
      if (cols.has(c) || diag1.has(r - c) || diag2.has(r + c)) continue;
      cols.add(c); diag1.add(r - c); diag2.add(r + c);
      dfs(r + 1);
      cols.delete(c); diag1.delete(r - c); diag2.delete(r + c);
    }
  }
  dfs(0);
  return count;
}

// Subset sum: find any subset summing to target
function subsetSum(a, target) {
  a.sort((x,y) => y - x); // order helps pruning
  function dfs(i, sum) {
    if (sum === target) return true;
    if (i === a.length || sum > target) return false;
    // choose
    if (dfs(i + 1, sum + a[i])) return true;
    // skip
    return dfs(i + 1, sum);
  }
  return dfs(0, 0);
}

Branch-and-bound augments backtracking with a bound function that estimates the best possible value achievable from a partial solution. If the bound is worse than the current best, prune the branch.

// 0/1 Knapsack via Branch-and-Bound (outline)
function knapsackBB(items, W) {
  items.sort((a,b) => b.v/b.w - a.v/a.w); // value density for bound
  let best = 0;
  function bound(i, w, v) {
    let value = v, weight = w;
    for (; i < items.length && weight + items[i].w <= W; i++) {
      weight += items[i].w; value += items[i].v;
    }
    if (i < items.length) value += (W - weight) * (items[i].v / items[i].w); // fractional
    return value;
  }
  function dfs(i, w, v) {
    best = Math.max(best, v);
    if (i === items.length || w > W) return;
    if (bound(i, w, v) <= best) return; // prune by bound
    // take item
    if (w + items[i].w <= W) dfs(i + 1, w + items[i].w, v + items[i].v);
    // skip item
    dfs(i + 1, w, v);
  }
  dfs(0, 0, 0);
  return best;
}

• Upper bounds: relax constraints (fractional/LP relaxation), admissible heuristics.
• Lower bounds: quickly construct any feasible solution to beat bounds.
• Ordering: explore promising branches first (best-first with PQ) to tighten best quickly.

1. N-Queens: generate all solutions and print boards.
2. Branch-and-bound TSP: implement with a tight lower bound (e.g., 1-tree bound).
3. Sudoku solver with constraint propagation and backtracking.