Backtracking

// Template 1: choose → explore → un-choose, with a start index.
// Lists every way to pick k numbers from 1..n. Each call only picks numbers bigger than the last one,
// so every combination is built exactly once ([1, 2] is never also built as [2, 1]).
export function combinations(n, k) {
  const result = [];
  const path = [];

  function backtrack(start) {
    if (path.length === k) {
      result.push([...path]);    // record a copy: path keeps changing after this
      return;
    }
    for (let i = start; i <= n; i++) {
      path.push(i);              // choose
      backtrack(i + 1);          // explore: only numbers after i
      path.pop();                // un-choose, so the next i starts from the same path
    }
  }

  backtrack(1);
  return result;
}

// Template 2: when order matters, every call may pick ANY item that is not already in the path.
// used[i] records whether items[i] is in the path, so the check is O(1). With k = items.length
// this lists every permutation.
export function arrangements(items, k = items.length) {
  const result = [];
  const path = [];
  const used = new Array(items.length).fill(false);

  function backtrack() {
    if (path.length === k) {
      result.push([...path]);
      return;
    }
    for (let i = 0; i < items.length; i++) {
      if (used[i]) continue;     // already placed in this path
      used[i] = true;            // choose
      path.push(items[i]);
      backtrack();               // explore
      path.pop();                // un-choose: undo both changes
      used[i] = false;
    }
  }

  backtrack();
  return result;
}

// Template 3: pruning. Lists every group of numbers (each used at most once) that adds up to target.
// The numbers are positive and distinct. Sorting first means that once a number is too big for what
// is left, every number after it is too: break, and the whole rest of the loop is skipped.
export function subsetsWithSum(nums, target) {
  const sorted = [...nums].sort((a, b) => a - b);
  const result = [];
  const path = [];

  function backtrack(start, remaining) {
    if (remaining === 0) {
      result.push([...path]);
      return;
    }
    for (let i = start; i < sorted.length; i++) {
      if (sorted[i] > remaining) break;          // prune this branch and all the ones after it
      path.push(sorted[i]);                      // choose
      backtrack(i + 1, remaining - sorted[i]);   // explore: i + 1, each number at most once
      path.pop();                                // un-choose
    }
  }

  backtrack(0, target);
  return result;
}

// Template 4: backtracking on a grid. Counts the paths from the top-left to the bottom-right cell that
// step only on open cells (0), move up/down/left/right, and never visit a cell twice.
// The grid itself is the visited set: mark a cell before exploring from it, restore it afterwards.
const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];

export function countPaths(grid) {
  const rows = grid.length;
  const cols = grid[0].length;

  function explore(r, c) {
    if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] !== 0) return 0; // off the board, wall or on the path
    if (r === rows - 1 && c === cols - 1) return 1;
    grid[r][c] = 2;                              // choose: this cell is on the current path
    let total = 0;
    for (const [dr, dc] of DIRS) total += explore(r + dr, c + dc); // explore
    grid[r][c] = 0;                              // un-choose: free the cell for other paths
    return total;
  }

  return explore(0, 0);
}