Backtracking

Backtracking is a refined brute force. It builds candidates for the solution incrementally and abandons ("backtracks") a candidate as soon as it determines the candidate cannot lead to a valid solution. This pruning is what separates backtracking from naive enumeration.

Think of it as a depth-first search through a state-space tree: each node is a partial solution, each edge is a choice, and leaves are complete candidates. Pruning cuts entire subtrees before reaching their leaves.

The Universal Template

Every backtracking algorithm follows the same three-step pattern at each node:

// Universal Backtracking Template
function backtrack(state, choices) {
  // Base case: state is a complete solution
  if (isSolution(state)) {
    result.push(copy(state));
    return;
  }

  for (const choice of choices) {
    // Pruning: skip invalid choices early
    if (!isValid(state, choice)) continue;

    // Choose: add this choice to state
    makeChoice(state, choice);

    // Explore: recurse with updated state
    backtrack(state, nextChoices(state, choice));

    // Unchoose: undo the choice (backtrack)
    undoChoice(state, choice);
  }
}

Note

The "unchoose" step is what makes backtracking work. After exploring a path, you must restore the state to exactly what it was before the choice, so the next sibling branch starts from a clean state.

N-Queens Problem

Place n queens on an n×n chessboard so no two queens attack each other (no two queens share a row, column, or diagonal).

State: current board — which column each row's queen is placed in Choice: which column to place the queen in the current row Pruning: skip columns that conflict with any previously placed queen

// N-Queens — complete solution with all boards
function solveNQueens(n) {
  const results = [];
  const queens = [];          // queens[row] = column where queen is placed

  function isValid(row, col) {
    for (let r = 0; r < row; r++) {
      const c = queens[r];
      if (c === col) return false;              // same column
      if (Math.abs(c - col) === row - r) return false;  // same diagonal
    }
    return true;
  }

  function backtrack(row) {
    if (row === n) {
      // Build board string representation
      const board = queens.map(col => {
        const rowArr = Array(n).fill('.');
        rowArr[col] = 'Q';
        return rowArr.join('');
      });
      results.push(board);
      return;
    }

    for (let col = 0; col < n; col++) {
      if (isValid(row, col)) {
        queens.push(col);    // choose
        backtrack(row + 1);  // explore
        queens.pop();        // unchoose
      }
    }
  }

  backtrack(0);
  return results;
}

const solutions = solveNQueens(4);
console.log(solutions.length);   // 2 solutions for 4×4
console.log(solutions[0]);
// ['.Q..', '...Q', 'Q...', '..Q.']

// Just count solutions (faster — no board building)
function totalNQueens(n) {
  let count = 0;
  const cols = new Set();
  const diag1 = new Set();  // row - col
  const diag2 = new Set();  // row + col

  function backtrack(row) {
    if (row === n) { count++; 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);
      backtrack(row + 1);
      cols.delete(col); diag1.delete(row - col); diag2.delete(row + col);
    }
  }

  backtrack(0);
  return count;
}

console.log(totalNQueens(8)); // 92

Sudoku Solver

Fill a 9×9 sudoku board so that each row, column, and 3×3 box contains digits 1–9 exactly once.

State: the board (9×9 grid, '.' for empty) Choice: which digit to place in the next empty cell Pruning: skip digits already used in the same row, column, or 3×3 box

// Sudoku Solver
function solveSudoku(board) {
  function isValid(row, col, num) {
    const char = String(num);
    const boxRow = Math.floor(row / 3) * 3;
    const boxCol = Math.floor(col / 3) * 3;

    for (let i = 0; i < 9; i++) {
      if (board[row][i] === char) return false;          // same row
      if (board[i][col] === char) return false;          // same column
      if (board[boxRow + Math.floor(i / 3)]
              [boxCol + (i % 3)] === char) return false; // same box
    }
    return true;
  }

  function backtrack() {
    // Find next empty cell
    for (let r = 0; r < 9; r++) {
      for (let c = 0; c < 9; c++) {
        if (board[r][c] !== '.') continue;

        for (let num = 1; num <= 9; num++) {
          if (isValid(r, c, num)) {
            board[r][c] = String(num);  // choose
            if (backtrack()) return true;
            board[r][c] = '.';          // unchoose
          }
        }

        return false;  // no valid digit fits — backtrack
      }
    }
    return true;  // all cells filled
  }

  backtrack();
}

Generate Parentheses

Generate all combinations of n pairs of well-formed parentheses.

Key insight: At any point during construction:

You can add ( if you have open parens remaining
You can add ) only if the number of close parens used so far is less than open parens used

// Generate Parentheses — O(4^n / sqrt(n)) — Catalan number
function generateParenthesis(n) {
  const result = [];

  function backtrack(current, open, close) {
    if (current.length === 2 * n) {
      result.push(current);
      return;
    }

    if (open < n) {
      backtrack(current + '(', open + 1, close);
    }
    if (close < open) {
      backtrack(current + ')', open, close + 1);
    }
  }

  backtrack('', 0, 0);
  return result;
}

console.log(generateParenthesis(3));
// ['((()))', '(()())', '(())()', '()(())', '()()()']
console.log(generateParenthesis(3).length); // 5 (5th Catalan number)

Permutations

Generate all permutations of an array of distinct integers.

// Permutations — O(n! · n)
function permute(nums) {
  const result = [];

  function backtrack(start) {
    if (start === nums.length) {
      result.push([...nums]);
      return;
    }

    for (let i = start; i < nums.length; i++) {
      [nums[start], nums[i]] = [nums[i], nums[start]];  // choose
      backtrack(start + 1);
      [nums[start], nums[i]] = [nums[i], nums[start]];  // unchoose
    }
  }

  backtrack(0);
  return result;
}

// Permutations II — with duplicates (use a frequency map)
function permuteUnique(nums) {
  const result = [];
  const freq = new Map();
  for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);

  function backtrack(current) {
    if (current.length === nums.length) {
      result.push([...current]);
      return;
    }
    for (const [num, count] of freq) {
      if (count === 0) continue;
      current.push(num);
      freq.set(num, count - 1);
      backtrack(current);
      current.pop();
      freq.set(num, count);
    }
  }

  backtrack([]);
  return result;
}

console.log(permute([1, 2, 3]).length);       // 6
console.log(permuteUnique([1, 1, 2]).length); // 3

Subsets

Generate all subsets (power set) of an array of unique integers. Unlike permutations, order does not matter — we only extend forward (the start index prevents duplicates).

// Subsets — O(n · 2^n)
function subsets(nums) {
  const result = [];

  function backtrack(start, current) {
    result.push([...current]);  // add the current subset at every node

    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]);          // choose
      backtrack(i + 1, current);      // explore (i+1 prevents re-using elements)
      current.pop();                  // unchoose
    }
  }

  backtrack(0, []);
  return result;
}

// Subsets II — with duplicates
function subsetsWithDup(nums) {
  nums.sort((a, b) => a - b);  // sort to group duplicates
  const result = [];

  function backtrack(start, current) {
    result.push([...current]);

    for (let i = start; i < nums.length; i++) {
      // Skip duplicates at the same recursion level
      if (i > start && nums[i] === nums[i - 1]) continue;
      current.push(nums[i]);
      backtrack(i + 1, current);
      current.pop();
    }
  }

  backtrack(0, []);
  return result;
}

console.log(subsets([1, 2, 3]).length);        // 8 (2^3)
console.log(subsetsWithDup([1, 2, 2]).length); // 6

Combination Sum

Find all unique combinations that sum to a target. Each number can be used multiple times.

Trick: Allow re-using the same index (pass i not i+1 when recurring), and prune when the running sum exceeds the target.

// Combination Sum — O(n^(target/min)) worst case
function combinationSum(candidates, target) {
  candidates.sort((a, b) => a - b);
  const result = [];

  function backtrack(start, current, remaining) {
    if (remaining === 0) {
      result.push([...current]);
      return;
    }

    for (let i = start; i < candidates.length; i++) {
      if (candidates[i] > remaining) break;  // sorted — prune early

      current.push(candidates[i]);
      backtrack(i, current, remaining - candidates[i]); // i (not i+1) = can reuse
      current.pop();
    }
  }

  backtrack(0, [], target);
  return result;
}

console.log(combinationSum([2, 3, 6, 7], 7));
// [[2,2,3], [7]]

Word Search in a Grid

Given an m×n grid of characters and a word, determine if the word exists in the grid, formed by sequentially adjacent cells (horizontal or vertical, no reuse of the same cell).

// Word Search — O(m · n · 4^L) where L = word length
function exist(board, word) {
  const m = board.length;
  const n = board[0].length;
  const dirs = [[0,1],[0,-1],[1,0],[-1,0]];

  function backtrack(r, c, idx) {
    if (idx === word.length) return true;  // found all chars
    if (r < 0 || r >= m || c < 0 || c >= n) return false;
    if (board[r][c] !== word[idx]) return false;

    const temp = board[r][c];
    board[r][c] = '#';  // mark as visited (choose)

    for (const [dr, dc] of dirs) {
      if (backtrack(r + dr, c + dc, idx + 1)) {
        board[r][c] = temp;  // restore before returning
        return true;
      }
    }

    board[r][c] = temp;  // unchoose
    return false;
  }

  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (backtrack(r, c, 0)) return true;
    }
  }

  return false;
}

const board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']];
console.log(exist(board, 'ABCCED')); // true
console.log(exist(board, 'SEE'));    // true
console.log(exist(board, 'ABCB'));   // false

Warning

Modifying the board in-place (`board[r][c] = '#'`) to mark visited cells is a common optimization that avoids allocating a separate `visited` array. Always restore the value after the recursive call completes.

Tip

For Word Search, an early termination optimization: count character frequencies in the board. If any character in `word` appears fewer times in the board than required, return false immediately without any DFS.

Backtracking Complexity

Problem	Time Complexity	Space (call stack)
N-Queens	O(n!)	O(n)
Sudoku Solver	O(9^(empty cells))	O(81)
Generate Parentheses	O(4^n / sqrt(n))	O(n)
Permutations	O(n! · n)	O(n)
Subsets	O(n · 2^n)	O(n)
Combination Sum	O(n^(T/min))	O(T/min)
Word Search	O(m · n · 4^L)	O(L)

Backtracking vs DFS vs DP

Backtracking = DFS with pruning — same traversal, but invalid branches are cut
DP caches results — use DP when the same subproblem appears multiple times
Backtracking explores the full tree (minus pruned branches) — no caching
Backtracking is best when the answer requires listing all valid configurations
Pruning effectiveness determines practical performance — good pruning makes O(n!) tractable