Topic Overview

Backtracking

Master backtracking: systematic exploration of solution space by trying partial solutions and undoing choices that don't lead to solutions.

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

function backtrack(currentState: State, ...args): void {
  // Base case: solution found
  if (isSolution(currentState)) {
    processSolution(currentState);
    return;
  }
  
  // Generate candidates
  const candidates = generateCandidates(currentState);
  
  for (const candidate of candidates) {
    // Make choice
    makeChoice(currentState, candidate);
    
    // Check constraint
    if (isValid(currentState)) {
      // Recurse
      backtrack(currentState, ...args);
    }
    
    // Undo choice (backtrack)
    undoChoice(currentState, candidate);
  }
}

Permutations

function permutations(nums: number[]): number[][] {
  const result: number[][] = [];
  const current: number[] = [];
  const used = new Set<number>();
  
  function backtrack(): void {
    // Base case: permutation complete
    if (current.length === nums.length) {
      result.push([...current]);
      return;
    }
    
    // Try each number
    for (const num of nums) {
      if (used.has(num)) continue; // Skip used
      
      // Make choice
      current.push(num);
      used.add(num);
      
      // Recurse
      backtrack();
      
      // Undo choice
      current.pop();
      used.delete(num);
    }
  }
  
  backtrack();
  return result;
}

// Time: O(n! * n)
// Space: O(n) for recursion stack

Combinations

function combinations(n: number, k: number): number[][] {
  const result: number[][] = [];
  const current: number[] = [];
  
  function backtrack(start: number): void {
    // Base case: combination complete
    if (current.length === k) {
      result.push([...current]);
      return;
    }
    
    // Try each number from start
    for (let i = start; i <= n; i++) {
      // Make choice
      current.push(i);
      
      // Recurse (next number must be > i)
      backtrack(i + 1);
      
      // Undo choice
      current.pop();
    }
  }
  
  backtrack(1);
  return result;
}

// Time: O(C(n,k) * k)
// Space: O(k)

N-Queens

function solveNQueens(n: number): string[][] {
  const result: string[][] = [];
  const board: number[] = []; // board[i] = column of queen in row i
  
  function isValid(row: number, col: number): boolean {
    // Check if queen at (row, col) conflicts with previous queens
    for (let i = 0; i < row; i++) {
      const prevCol = board[i];
      
      // Same column
      if (prevCol === col) return false;
      
      // Same diagonal
      if (Math.abs(prevCol - col) === Math.abs(i - row)) {
        return false;
      }
    }
    
    return true;
  }
  
  function backtrack(row: number): void {
    // Base case: all queens placed
    if (row === n) {
      // Convert to string representation
      const solution: string[] = [];
      for (const col of board) {
        const rowStr = '.'.repeat(col) + 'Q' + '.'.repeat(n - col - 1);
        solution.push(rowStr);
      }
      result.push(solution);
      return;
    }
    
    // Try each column
    for (let col = 0; col < n; col++) {
      if (isValid(row, col)) {
        // Make choice
        board.push(col);
        
        // Recurse
        backtrack(row + 1);
        
        // Undo choice
        board.pop();
      }
    }
  }
  
  backtrack(0);
  return result;
}

// Time: O(n!)
// Space: O(n)

Examples

function exist(board: string[][], word: string): boolean {
  const rows = board.length;
  const cols = board[0].length;
  const visited: boolean[][] = Array(rows).fill(null).map(() => Array(cols).fill(false));
  
  function backtrack(row: number, col: number, index: number): boolean {
    // Base case: word found
    if (index === word.length) {
      return true;
    }
    
    // Boundary check
    if (row < 0 || row >= rows || col < 0 || col >= cols) {
      return false;
    }
    
    // Already visited or doesn't match
    if (visited[row][col] || board[row][col] !== word[index]) {
      return false;
    }
    
    // Make choice
    visited[row][col] = true;
    
    // Try all directions
    const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    for (const [dr, dc] of directions) {
      if (backtrack(row + dr, col + dc, index + 1)) {
        return true;
      }
    }
    
    // Undo choice
    visited[row][col] = false;
    return false;
  }
  
  // Try starting from each cell
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (backtrack(i, j, 0)) {
        return true;
      }
    }
  }
  
  return false;
}

Sudoku Solver

function solveSudoku(board: string[][]): void {
  function isValid(row: number, col: number, num: string): boolean {
    // Check row
    for (let j = 0; j < 9; j++) {
      if (board[row][j] === num) return false;
    }
    
    // Check column
    for (let i = 0; i < 9; i++) {
      if (board[i][col] === num) return false;
    }
    
    // Check 3x3 box
    const boxRow = Math.floor(row / 3) * 3;
    const boxCol = Math.floor(col / 3) * 3;
    for (let i = boxRow; i < boxRow + 3; i++) {
      for (let j = boxCol; j < boxCol + 3; j++) {
        if (board[i][j] === num) return false;
      }
    }
    
    return true;
  }
  
  function backtrack(): boolean {
    for (let i = 0; i < 9; i++) {
      for (let j = 0; j < 9; j++) {
        if (board[i][j] === '.') {
          // Try each number
          for (let num = 1; num <= 9; num++) {
            const numStr = num.toString();
            
            if (isValid(i, j, numStr)) {
              // Make choice
              board[i][j] = numStr;
              
              // Recurse
              if (backtrack()) {
                return true;
              }
              
              // Undo choice
              board[i][j] = '.';
            }
          }
          
          return false; // No valid number
        }
      }
    }
    
    return true; // All cells filled
  }
  
  backtrack();
}

Subset Generation

function subsets(nums: number[]): number[][] {
  const result: number[][] = [];
  const current: number[] = [];
  
  function backtrack(index: number): void {
    // Add current subset
    result.push([...current]);
    
    // Try each remaining element
    for (let i = index; i < nums.length; i++) {
      // Make choice
      current.push(nums[i]);
      
      // Recurse
      backtrack(i + 1);
      
      // Undo choice
      current.pop();
    }
  }
  
  backtrack(0);
  return result;
}

// Time: O(2^n * n)
// Space: O(n)

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:

FeatureRegular RecursionBacktracking
PurposeSolve problemExplore solution space
UndoNo undo neededMust undo choices
StateState passed downState modified and restored
Use caseTree traversal, divide-conquerConstraint satisfaction, search

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

Key Takeaways

  • 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

About the author

InterviewCrafted helps you master system design with patience. We believe in curiosity-led engineering, reflective writing, and designing systems that make future changes feel calm.