Backtracking

Backtracking is an algorithmic technique for solving problems by trying partial solutions and abandoning them ("backtracking") if they cannot lead to a valid solution.

Why This Matters in Interviews

Backtracking is essential because:

• Constraint satisfaction: Many problems are constraint satisfaction problems
• Combinatorial problems: Permutations, combinations, subsets
• Search problems: Finding all solutions or one solution
• Problem-solving: Tests recursive thinking and optimization

Interviewers use backtracking to assess your ability to systematically explore solution spaces, handle constraints, and optimize recursive solutions.

Core Concepts

• State space tree: Tree of all possible solutions
• Pruning: Eliminate branches that can't lead to solution
• Choice: Make a decision at each step
• Constraint: Check if current choice is valid
• Backtrack: Undo choice and try next option
• Base case: Solution found or no more choices
• Memoization: Cache results to avoid redundant work

Detailed Explanation

Backtracking Template

1function backtrack(currentState: State, ...args): void {
2  // Base case: solution found
3  if (isSolution(currentState)) {
4    processSolution(currentState);
5    return;
6  }
7  
8  // Generate candidates
9  const candidates = generateCandidates(currentState);
10  
11  for (const candidate of candidates) {
12    // Make choice
13    makeChoice(currentState, candidate);
14    
15    // Check constraint
16    if (isValid(currentState

Permutations

1function permutations(nums: number[]): number[][] {
2  const result: number[][] = [];
3  const current: number[] = [];
4  const used = new Set<number>();
5  
6  function backtrack(): void {
7    // Base case: permutation complete
8    if (current.length === nums.length)

Combinations

1function combinations(n: number, k: number): number[][] {
2  const result: number[][] = [];
3  const current: number[] = [];
4  
5  function backtrack(start: number): void {
6    // Base case: combination complete
7    if (current.length === k) {
8      result.push([...current])

N-Queens

1function solveNQueens(n: number): string[][] {
2  const result: string[][] = [];
3  const board: number[] = []; // board[i] = column of queen in row i
4  
5  function isValid(row: number, col: number): boolean {
6    // Check if queen at (row, col) conflicts with previous queens
7    for (let i = 0; i < row; i++) {
8       prevCol  boardi

Examples

Word Search

1function exist(board: string[][], word: string): boolean {
2  const rows = board.length;
3  const cols = board[0].length;
4  const visited: boolean[][] = Array(rows).fill(null).map(() => Array(cols).fill(false));
5  
6  function backtrackrow  col  index

Sudoku Solver

1function solveSudoku(board: string[][]): void {
2  function isValid(row: number, col: number, num: string): boolean {
3    // Check row
4    for (let j = 0; j < 9; j++) {
5      if (board[row][j] === num) return false;
6    }
7    
8    // Check column
9    for (let i =  i   i

Subset Generation

1function subsets(nums: number[]): number[][] {
2  const result: number[][] = [];
3  const current: number[] = [];
4  
5  function backtrack(index: number): void {
6    // Add current subset
7    result.push([...current]);
8    
9    // Try each remaining element
10    for (let i  index i  numslength i

Common Pitfalls

• Not undoing choices: State persists, wrong results. Fix: Always undo after recursion
• Wrong constraint checking: Allowing invalid states. Fix: Check constraints before recursing
• Inefficient pruning: Not pruning early enough. Fix: Check constraints as early as possible
• Copying state incorrectly: Modifying shared state. Fix: Use copies or undo properly
• Infinite recursion: No base case or wrong termination. Fix: Always define base case
• Redundant work: Not memoizing when possible. Fix: Cache results for repeated subproblems

Interview Questions

Beginner

Q: What is backtracking and how does it differ from regular recursion?

A:

Backtracking is a systematic way to explore solution space by:

1. Making a choice
2. Recursively solving with that choice
3. Undoing the choice (backtracking) if it doesn't lead to solution
4. Trying next choice

Difference from Recursion:

Example:

Regular Recursion (Tree traversal):

function traverse(node) {
  if (!node) return;
  process(node);
  traverse(node.left);
  traverse(node.right);
  // No undo needed
}

Backtracking (Permutations):

function backtrack(current) {
  if (isComplete(current)) {
    saveSolution(current);
    return;
  }
  
  for (choice in choices) {
    makeChoice(current, choice);  // Modify state
    backtrack(current);
    undoChoice(current, choice);  // Restore state
  }
}

Key points:

• State modification: Backtracking modifies and restores state
• Systematic exploration: Tries all possibilities
• Constraint checking: Validates choices before recursing

Intermediate

Q: Implement a backtracking solution for the N-Queens problem. How do you optimize it?

A:

function solveNQueens(n: number): string[][] {
  const result: string[][] = [];
  const board: number[] = []; // board[i] = column of queen in row i
  
  // Optimized constraint checking
  const cols = new Set<number>();
  const diag1 = new Set<number>(); // row - col
  const diag2 = new Set<number>(); // row + col
  
  function isValid(row: number, col: number): boolean {
    return !cols.has(col) &&
           !diag1.has(row - col) &&
           !diag2.has(row + col);
  }
  
  function makeChoice(row: number, col: number): void {
    board.push(col);
    cols.add(col);
    diag1.add(row - col);
    diag2.add(row + col);
  }
  
  function undoChoice(row: number, col: number): void {
    board.pop();
    cols.delete(col);
    diag1.delete(row - col);
    diag2.delete(row + col);
  }
  
  function backtrack(row: number): void {
    if (row === n) {
      // Convert to string representation
      const solution: string[] = [];
      for (const col of board) {
        solution.push('.'.repeat(col) + 'Q' + '.'.repeat(n - col - 1));
      }
      result.push(solution);
      return;
    }
    
    for (let col = 0; col < n; col++) {
      if (isValid(row, col)) {
        makeChoice(row, col);
        backtrack(row + 1);
        undoChoice(row, col);
      }
    }
  }
  
  backtrack(0);
  return result;
}

// Optimizations:
// 1. Use sets for O(1) constraint checking
// 2. Early termination if only need one solution
// 3. Symmetry breaking (only try first half of first row)
// 4. Bit manipulation for even faster checking

Optimized with bit manipulation:

function solveNQueensBit(n: number): number {
  let count = 0;
  
  function backtrack(row: number, cols: number, diag1: number, diag2: number): void {
    if (row === n) {
      count++;
      return;
    }
    
    // Available positions
    let available = ((1 << n) - 1) & (~(cols | diag1 | diag2));
    
    while (available) {
      // Get rightmost available position
      const pos = available & -available;
      available -= pos;
      
      // Recurse
      backtrack(
        row + 1,
        cols | pos,
        (diag1 | pos) << 1,
        (diag2 | pos) >> 1
      );
    }
  }
  
  backtrack(0, 0, 0, 0);
  return count;
}

Senior

Q: Design a constraint satisfaction solver using backtracking that handles millions of variables and constraints. How do you optimize variable ordering, value ordering, and constraint propagation?

A:

class ConstraintSatisfactionSolver {
  private variables: Map<string, Variable>;
  private constraints: Constraint[];
  private assignments: Map<string, any>;
  
  constructor(variables: Map<string, Variable>, constraints: Constraint[]) {
    this.variables = variables;
    this.constraints = constraints;
    this.assignments = new Map();
  }
  
  solve(): Map<string, any> | null {
    return this.backtrack();
  }
  
  private backtrack(): Map<string, any> | null {
    // Check if complete
    if (this.isComplete()) {
      return new Map(this.assignments);
    }
    
    // Select unassigned variable (MRV - Minimum Remaining Values)
    const variable = this.selectUnassignedVariable();
    if (!variable) return null;
    
    // Try values in order (LCV - Least Constraining Value)
    const values = this.orderValues(variable);
    
    for (const value of values) {
      // Make assignment
      this.assignments.set(variable.name, value);
      
      // Forward checking / constraint propagation
      const inferences = this.inference(variable, value);
      
      if (inferences !== null) {
        // Apply inferences
        for (const [varName, val] of inferences) {
          this.assignments.set(varName, val);
        }
        
        // Recurse
        const result = this.backtrack();
        if (result !== null) {
          return result;
        }
        
        // Undo inferences
        for (const [varName] of inferences) {
          this.assignments.delete(varName);
        }
      }
      
      // Undo assignment
      this.assignments.delete(variable.name);
    }
    
    return null;
  }
  
  // MRV: Choose variable with fewest remaining values
  private selectUnassignedVariable(): Variable | null {
    let best: Variable | null = null;
    let minRemaining = Infinity;
    
    for (const variable of this.variables.values()) {
      if (this.assignments.has(variable.name)) continue;
      
      const remaining = this.countRemainingValues(variable);
      if (remaining < minRemaining) {
        minRemaining = remaining;
        best = variable;
      }
    }
    
    return best;
  }
  
  // LCV: Order values by how many options they leave for neighbors
  private orderValues(variable: Variable): any[] {
    const values = variable.domain.slice();
    
    return values.sort((a, b) => {
      const conflictsA = this.countConflicts(variable, a);
      const conflictsB = this.countConflicts(variable, b);
      return conflictsA - conflictsB; // Less conflicts first
    });
  }
  
  // Constraint propagation (forward checking)
  private inference(variable: Variable, value: any): Map<string, any> | null {
    const inferences = new Map<string, any>();
    
    // Check constraints involving this variable
    for (const constraint of this.constraints) {
      if (!constraint.involves(variable.name)) continue;
      
      const otherVar = constraint.getOtherVariable(variable.name);
      if (!otherVar || this.assignments.has(otherVar.name)) continue;
      
      // Remove inconsistent values from other variable's domain
      const remaining = otherVar.domain.filter(val => 
        constraint.isSatisfied(variable.name, value, otherVar.name, val)
      );
      
      if (remaining.length === 0) {
        // Domain wipeout - backtrack
        return null;
      }
      
      if (remaining.length === 1) {
        // Only one value left - must assign it
        inferences.set(otherVar.name, remaining[0]);
      }
    }
    
    return inferences;
  }
  
  // Arc consistency (AC-3 algorithm)
  private enforceArcConsistency(): boolean {
    const queue: [Variable, Variable][] = [];
    
    // Initialize queue with all arcs
    for (const constraint of this.constraints) {
      const vars = constraint.getVariables();
      if (vars.length === 2) {
        queue.push([vars[0], vars[1]]);
        queue.push([vars[1], vars[0]]);
      }
    }
    
    while (queue.length > 0) {
      const [xi, xj] = queue.shift()!;
      
      if (this.revise(xi, xj)) {
        if (xi.domain.length === 0) {
          return false; // No solution
        }
        
        // Add arcs back to queue
        for (const constraint of this.constraints) {
          if (constraint.involves(xi.name)) {
            const xk = constraint.getOtherVariable(xi.name);
            if (xk && xk !== xj) {
              queue.push([xk, xi]);
            }
          }
        }
      }
    }
    
    return true;
  }
  
  private revise(xi: Variable, xj: Variable): boolean {
    let revised = false;
    const toRemove: any[] = [];
    
    for (const value of xi.domain) {
      // Check if any value in xj.domain makes (xi, xj) consistent
      let hasSupport = false;
      
      for (const constraint of this.constraints) {
        if (constraint.involves(xi.name) && constraint.involves(xj.name)) {
          for (const valJ of xj.domain) {
            if (constraint.isSatisfied(xi.name, value, xj.name, valJ)) {
              hasSupport = true;
              break;
            }
          }
        }
      }
      
      if (!hasSupport) {
        toRemove.push(value);
        revised = true;
      }
    }
    
    // Remove values
    xi.domain = xi.domain.filter(v => !toRemove.includes(v));
    return revised;
  }
  
  private isComplete(): boolean {
    return this.assignments.size === this.variables.size;
  }
  
  private countRemainingValues(variable: Variable): number {
    return variable.domain.filter(val => 
      this.isConsistent(variable.name, val)
    ).length;
  }
  
  private countConflicts(variable: Variable, value: any): number {
    // Count how many constraints this value violates
    let conflicts = 0;
    for (const constraint of this.constraints) {
      if (constraint.involves(variable.name) && 
          !this.isConsistentWithConstraint(variable, value, constraint)) {
        conflicts++;
      }
    }
    return conflicts;
  }
  
  private isConsistent(varName: string, value: any): boolean {
    // Check all constraints
    for (const constraint of this.constraints) {
      if (constraint.involves(varName)) {
        if (!this.isConsistentWithConstraint(
          this.variables.get(varName)!,
          value,
          constraint
        )) {
          return false;
        }
      }
    }
    return true;
  }
  
  private isConsistentWithConstraint(
    variable: Variable,
    value: any,
    constraint: Constraint
  ): boolean {
    // Implementation depends on constraint type
    return true;
  }
}

interface Variable {
  name: string;
  domain: any[];
}

interface Constraint {
  involves(varName: string): boolean;
  getOtherVariable(varName: string): Variable | null;
  getVariables(): Variable[];
  isSatisfied(var1: string, val1: any, var2: string, val2: any): boolean;
}

Optimizations:

1. MRV (Minimum Remaining Values): Choose variable with fewest options
2. LCV (Least Constraining Value): Try values that leave most options
3. Forward checking: Propagate constraints immediately
4. Arc consistency: Enforce consistency before backtracking
5. Constraint learning: Learn new constraints from failures

• Backtracking: Systematic exploration by trying choices and undoing
• Template: Make choice → recurse → undo choice
• Constraint checking: Validate before recursing
• Pruning: Eliminate invalid branches early
• State management: Must undo choices to restore state
• Optimization: Variable/value ordering, constraint propagation
• Applications: Permutations, combinations, constraint satisfaction, puzzles