10 — Backtracking

What is Backtracking?

Build solutions incrementally, abandon (prune) paths that can't lead to valid solutions.

Explore → Check constraints → Valid? → Continue / Backtrack

                    []
                 /  |  \
               1    2    3
              / \   |
            1,2  1,3  2,3
            |
          1,2,3

---

Template

function backtrack(result: any[], current: any[], choices: any[], ...constraints) {
  if (isComplete(current)) {
    result.push([...current]); // Found valid solution
    return;
  }
  
  for (const choice of choices) {
    if (!isValid(choice, current)) continue; // Prune
    
    current.push(choice);          // Choose
    backtrack(result, current, ...); // Explore
    current.pop();                 // Unchoose (backtrack)
  }
}

---

Permutations

function permute(nums: number[]): number[][] {
  const result: number[][] = [];
  const used = new Array(nums.length).fill(false);
  
  function backtrack(current: number[]) {
    if (current.length === nums.length) {
      result.push([...current]);
      return;
    }
    
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true;
      current.push(nums[i]);
      backtrack(current);
      current.pop();
      used[i] = false;
    }
  }
  
  backtrack([]);
  return result;
}
// permute([1,2,3]) → [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

---

Subsets

function subsets(nums: number[]): number[][] {
  const result: number[][] = [];
  
  function backtrack(start: number, current: number[]) {
    result.push([...current]);
    
    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]);
      backtrack(i + 1, current);
      current.pop();
    }
  }
  
  backtrack(0, []);
  return result;
}
// subsets([1,2,3]) → [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]

---

Combination Sum

// Find combinations that sum to target (can reuse elements)
function combinationSum(candidates: number[], target: number): number[][] {
  const result: number[][] = [];
  
  function backtrack(start: number, current: number[], remaining: number) {
    if (remaining === 0) { result.push([...current]); return; }
    if (remaining < 0) return;
    
    for (let i = start; i < candidates.length; i++) {
      current.push(candidates[i]);
      backtrack(i, current, remaining - candidates[i]); // i, not i+1 (reuse allowed)
      current.pop();
    }
  }
  
  backtrack(0, [], target);
  return result;
}

---

N-Queens

function solveNQueens(n: number): string[][] {
  const result: string[][] = [];
  const cols = new Set<number>();
  const diag1 = new Set<number>(); // row - col
  const diag2 = new Set<number>(); // row + col
  const board = Array.from({ length: n }, () => '.'.repeat(n));
  
  function backtrack(row: number) {
    if (row === n) {
      result.push([...board]);
      return;
    }
    
    for (let col = 0; col < n; col++) {
      if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) continue;
      
      cols.add(col); diag1.add(row - col); diag2.add(row + col);
      board[row] = '.'.repeat(col) + 'Q' + '.'.repeat(n - col - 1);
      
      backtrack(row + 1);
      
      cols.delete(col); diag1.delete(row - col); diag2.delete(row + col);
      board[row] = '.'.repeat(n);
    }
  }
  
  backtrack(0);
  return result;
}

---

Sudoku Solver

function solveSudoku(board: string[][]): void {
  function isValid(row: number, col: number, ch: string): boolean {
    const boxRow = 3 * Math.floor(row / 3);
    const boxCol = 3 * Math.floor(col / 3);
    
    for (let i = 0; i < 9; i++) {
      if (board[row][i] === ch) return false;
      if (board[i][col] === ch) return false;
      if (board[boxRow + Math.floor(i / 3)][boxCol + (i % 3)] === ch) return false;
    }
    return true;
  }
  
  function solve(): boolean {
    for (let r = 0; r < 9; r++) {
      for (let c = 0; c < 9; c++) {
        if (board[r][c] !== '.') continue;
        
        for (let d = 1; d <= 9; d++) {
          const ch = String(d);
          if (!isValid(r, c, ch)) continue;
          
          board[r][c] = ch;
          if (solve()) return true;
          board[r][c] = '.'; // Backtrack
        }
        return false; // No valid digit → backtrack
      }
    }
    return true; // All cells filled
  }
  
  solve();
}

---

Pruning Strategies

1. Skip duplicates (sorted array):
   if (i > start && nums[i] === nums[i-1]) continue;

2. Early termination:
   if (currentSum > target) return;  // Can't improve

3. Constraint checking:
   if (!isValid(choice)) continue;   // Don't explore invalid paths

4. Sorting first:
   Sort to enable duplicate skipping and early termination

---

Key Takeaways

• Backtracking = try → check → continue or undo
• Permutations: use used[] array; Subsets/Combinations: use start index
• Pruning is critical — skip invalid paths early to avoid exponential blowup
• Use Sets for O(1) constraint checking (columns, diagonals)
• Always [...current] when pushing to results (avoid reference issues)
• Time complexity is typically exponential — but pruning makes it practical