The choose-explore-unchoose template, pruning strategies, and classic problems — permutations, combinations, subsets, N-Queens

Backtracking

Backtracking is a systematic way to explore all possible solutions by building candidates incrementally and abandoning ("backtracking") a candidate as soon as it cannot lead to a valid solution. It is essentially a depth-first search on the decision tree.

When to use backtracking:

The problem asks to enumerate all valid solutions (subsets, permutations, combinations)
The problem has constraints that allow early pruning
Brute force would be exponential but many branches can be eliminated

When NOT to use backtracking:

You only need the count or optimal value → use DP instead
No constraint to prune → backtracking degenerates into brute force

The template

Every backtracking solution follows this pattern:

function backtrack(state: State, choices: Choice[]): void {
  if (isGoal(state)) {
    results.push(copy(state));
    return;
  }

  for (const choice of choices) {
    if (!isValid(choice, state)) continue; // prune

    makeChoice(state, choice);       // choose
    backtrack(state, nextChoices);    // explore
    undoChoice(state, choice);       // unchoose (backtrack)
  }
}

The three key operations:

Choose — add the current choice to the candidate
Explore — recurse with the updated candidate
Unchoose — remove the choice to try the next option

Subsets

Generate all subsets of a set. For each element, decide: include or skip.

function subsets(nums: number[]): number[][] {
  const result: number[][] = [];

  function backtrack(start: number, current: number[]): void {
    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;
}

Key insight: start parameter ensures we only look forward, avoiding duplicates.

Subsets with duplicates

Sort first, then skip consecutive equal elements at the same decision level:

function subsetsWithDup(nums: number[]): number[][] {
  nums.sort((a, b) => a - b);
  const result: number[][] = [];

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

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

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

Combinations

Choose k elements from n. Like subsets but with a fixed target size.

function combine(n: number, k: number): number[][] {
  const result: number[][] = [];

  function backtrack(start: number, current: number[]): void {
    if (current.length === k) {
      result.push([...current]);
      return;
    }

    // pruning: not enough remaining elements
    const remaining = n - start + 1;
    const needed = k - current.length;
    if (remaining < needed) return;

    for (let i = start; i <= n; i++) {
      current.push(i);
      backtrack(i + 1, current);
      current.pop();
    }
  }

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

Permutations

Order matters. Every element must appear exactly once.

function permute(nums: number[]): number[][] {
  const result: number[][] = [];
  const used = new Array(nums.length).fill(false);

  function backtrack(current: number[]): void {
    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;
}

Permutations with duplicates

Sort + skip rule: at the same recursion level, skip a number if it equals the previous number and the previous was not used (meaning we already explored that branch).

function permuteUnique(nums: number[]): number[][] {
  nums.sort((a, b) => a - b);
  const result: number[][] = [];
  const used = new Array(nums.length).fill(false);

  function backtrack(current: number[]): void {
    if (current.length === nums.length) {
      result.push([...current]);
      return;
    }

    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;
      used[i] = true;
      current.push(nums[i]);
      backtrack(current);
      current.pop();
      used[i] = false;
    }
  }

  backtrack([]);
  return result;
}

N-Queens

Place N queens on an N×N board such that no two attack each other.

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: number[] = []; // board[row] = col of queen

  function backtrack(row: number): void {
    if (row === n) {
      result.push(board.map(col => '.'.repeat(col) + 'Q' + '.'.repeat(n - col - 1)));
      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.push(col);

      backtrack(row + 1);

      board.pop();
      cols.delete(col);
      diag1.delete(row - col);
      diag2.delete(row + col);
    }
  }

  backtrack(0);
  return result;
}

Pruning: three sets track attacked columns and diagonals. Without this pruning, we would explore N^N states instead of a manageable search space.

Sudoku solver

Fill a 9×9 grid so each row, column, and 3×3 box contains 1-9.

function solveSudoku(board: string[][]): void {
  function isValid(row: number, col: number, num: string): boolean {
    for (let i = 0; i < 9; i++) {
      if (board[row][i] === num) return false;
      if (board[i][col] === num) return false;
    }
    const boxRow = Math.floor(row / 3) * 3;
    const boxCol = Math.floor(col / 3) * 3;
    for (let i = 0; i < 3; i++) {
      for (let j = 0; j < 3; j++) {
        if (board[boxRow + i][boxCol + 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] !== '.') continue;
        for (let num = 1; num <= 9; num++) {
          const ch = String(num);
          if (!isValid(i, j, ch)) continue;
          board[i][j] = ch;
          if (backtrack()) return true;
          board[i][j] = '.';
        }
        return false; // no valid number for this cell
      }
    }
    return true; // all cells filled
  }

  backtrack();
}

Pruning strategies

Pruning is what makes backtracking practical. Without it, you have brute force.

Strategy	How it works	Example
Constraint checking	Skip choices that violate rules	N-Queens: skip attacked positions
Bound checking	Skip if remaining capacity cannot reach goal	Combinations: not enough elements left
Sorting + dedup	Sort input, skip same-value choices at same level	Subsets/perms with duplicates
Early termination	Return as soon as a solution is found (if only one needed)	Sudoku: return true on first solution
Value ordering	Try most-constrained choices first	Sudoku: fill cells with fewest candidates first

Backtracking vs. DP

	Backtracking	Dynamic Programming
Goal	Enumerate all solutions	Find optimal value or count
Approach	Explore decision tree, prune invalid branches	Build solution from overlapping subproblems
Time	Often exponential (but pruned)	Polynomial (usually)
Use when	Need actual solutions, not just count	Need count or optimum, subproblems overlap

If a problem asks "how many ways" and has overlapping subproblems, prefer DP. If it asks "list all valid configurations," use backtracking.

Complexity

Backtracking complexity depends heavily on pruning effectiveness:

Subsets: O(2^n) — every element is included or not
Permutations: O(n!) — n choices for first, n-1 for second, etc.
N-Queens: ~O(n!) with pruning, much less in practice
Sudoku: O(9^m) where m is empty cells, heavily pruned in practice

Backtracking

On this page