Backtracking

Maze:  S → A → B → dead end
                ↑
       S → A → C → D → exit ✓  (backtracked from B, tried C)

function backtrack(state, choices) {
  // Base case: is the current state a complete valid solution?
  if (isComplete(state)) {
    results.push([...state]); // save a copy (not a reference!)
    return;
  }
 
  for (const choice of choices) {
    if (!isValid(state, choice)) continue; // pruning: skip bad choices
 
    // Choose
    state.push(choice);
 
    // Explore: recurse with the updated state
    backtrack(state, nextChoices(state, choice));
 
    // Unchoose: undo the choice (backtrack!)
    state.pop();
  }
}

                    []
          ┌─────────┼─────────┐
         [1]       [2]       [3]
        ┌───┐    ┌───┐    ┌───┐
      [1,2][1,3][2,1][2,3][3,1][3,2]
       ↓    ↓    ↓    ↓    ↓    ↓
[1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]
 
6 permutations = 3! ✓
Each leaf is a complete solution.

function permutations(nums) {
  const results = [];
 
  function backtrack(current, remaining) {
    if (!remaining.length) { results.push([...current]); return; }
    for (let i = 0; i < remaining.length; i++) {
      current.push(remaining[i]);                         // choose
      backtrack(current, remaining.filter((_, j) => j !== i)); // explore
      current.pop();                                      // unchoose
    }
  }
 
  backtrack([], nums);
  return results;
}

nums = [1, 2, 3]
 
                 []
         ┌───────────┐
      exclude 1   include 1
        [  ]         [1]
      ┌──┴──┐      ┌──┴──┐
   excl2  incl2  excl2  incl2
    []     [2]   [1]   [1,2]
  ┌─┴─┐  ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
  []  [3][2] [2,3][1][1,3][1,2][1,2,3]
 
Result: [], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]

function subsets(nums) {
  const results = [];
 
  function backtrack(start, current) {
    results.push([...current]); // every state (including empty) is valid
    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]); // choose
      backtrack(i + 1, current); // explore (i+1 to avoid reuse)
      current.pop(); // unchoose
    }
  }
 
  backtrack(0, []);
  return results;
}

function combinations(n, k) {
  const results = [];
 
  function backtrack(start, current) {
    if (current.length === k) { results.push([...current]); return; }
    // Pruning: don't start if there aren't enough numbers left
    for (let i = start; i <= n - (k - current.length) + 1; i++) {
      current.push(i);       // choose
      backtrack(i + 1, current); // explore
      current.pop();         // unchoose
    }
  }
 
  backtrack(1, []);
  return results;
}

function solveNQueens(n) {
  const results = [];
  const cols = new Set(), diag1 = new Set(), diag2 = new Set();
  // diag1: top-left to bottom-right (row - col is constant)
  // diag2: top-right to bottom-left (row + col is constant)
 
  function backtrack(row, board) {
    if (row === n) {
      results.push(board.map(cols => '.'.repeat(n).split('')
        .map((_, c) => c === cols ? 'Q' : '.').join('')));
      return;
    }
    for (let col = 0; col < n; col++) {
      if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) continue; // prune
      cols.add(col); diag1.add(row - col); diag2.add(row + col); board.push(col);
      backtrack(row + 1, board); // explore next row
      cols.delete(col); diag1.delete(row - col); diag2.delete(row + col); board.pop();
    }
  }
 
  backtrack(0, []);
  return results;
}

Combination Sum: find subsets of [2, 3, 6, 7] that sum to 7
 
Prune rule: if current sum > target, stop exploring this branch.
 
[2] → sum=2
  [2,2] → sum=4
    [2,2,2] → sum=6
      [2,2,2,2] → sum=8 > 7 ✗ PRUNE (don't go deeper)
      [2,2,2,3] → sum=9 > 7 ✗ PRUNE
    [2,2,3] → sum=7 ✓ RESULT
  [2,3] → sum=5
    [2,3,3] → sum=8 > 7 ✗ PRUNE
  ...
[7] → sum=7 ✓ RESULT

function combinationSum(candidates, target) {
  candidates.sort((a, b) => a - b); // sort enables early termination
  const results = [];
 
  function backtrack(start, current, remaining) {
    if (remaining === 0) { results.push([...current]); return; }
    for (let i = start; i < candidates.length; i++) {
      if (candidates[i] > remaining) break; // pruning: sorted, so rest will also be too big
      current.push(candidates[i]);
      backtrack(i, current, remaining - candidates[i]); // i (not i+1): can reuse
      current.pop();
    }
  }
 
  backtrack(0, [], target);
  return results;
}