Backtracking Explained

Backtracking is an algorithmic technique that incrementally builds candidates toward a solution and abandons a branch as soon as it becomes invalid. It is the standard approach for constraint-satisfaction problems like subsets, permutations, N-Queens, and Sudoku, and follows one template you can reuse across the whole topic.

The Choice-Explore-Undo Template

1. Choose : pick the next candidate to add to the partial solution.
2. Explore : recurse on the new partial solution.
3. Undo : remove the choice so sibling branches start fresh.

This sample of the decision tree for subsets of [1,2] shows how each path either includes or excludes an element:

graph TD
    R["[]"] --> I1["[1]"]
    R --> E1["[2]"]
    I1 --> I2["[1,2]"]
    I1 --> E2["[1]"]
    E1 --> I3["[2,1]"]
    E1 --> E3["[2]"]
    style R fill:#D97A2B,stroke:#B86418,color:#fff

Subsets

Every element is either in or out, so each leaf is a valid subset. Clone the current path before pushing it into the result.

function subsets(nums: number[]): number[][] {
  const res: number[][] = [];
  const path: number[] = [];
  const dfs = (start: number) => {
    res.push([...path]);
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);      // choose
      dfs(i + 1);              // explore
      path.pop();              // undo
    }
  };
  dfs(0);
  return res;
}
// Time: O(n * 2^n), Space: O(n)

Permutations

Unlike subsets, order matters and every element must be used exactly once. Track which indices are already chosen.

function permute(nums: number[]): number[][] {
  const res: number[][] = [];
  const path: number[] = [];
  const used = new Array(nums.length).fill(false);
  const dfs = () => {
    if (path.length === nums.length) { res.push([...path]); return; }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true;          // choose
      path.push(nums[i]);
      dfs();                   // explore
      path.pop();
      used[i] = false;         // undo
    }
  };
  dfs();
  return res;
}
// Time: O(n * n!), Space: O(n)

Combinations and the Start-Index Rule

Combinations are subsets of a fixed size K. Passing start enforces ordering so [1,2] and [2,1] are not both generated. This one parameter turns a permutation solver into a combination solver.

function combine(n: number, k: number): number[][] {
  const res: number[][] = [];
  const path: number[] = [];
  const dfs = (start: number) => {
    if (path.length === k) { res.push([...path]); return; }
    for (let i = start; i <= n; i++) {
      path.push(i);
      dfs(i + 1);
      path.pop();
    }
  };
  dfs(1);
  return res;
}

N-Queens: Constant-Time Constraint Checks

Place queens row by row, tracking columns, diagonals and anti-diagonals. The backtrack happens when a square is under attack.

function solveNQueens(n: number): string[][] {
  const res: string[][] = [];
  const cols = new Set<number>();
  const diag = new Set<number>(); // row - col
  const anti = new Set<number>(); // row + col
  const board: string[][] = Array.from({ length: n }, () => '.'.repeat(n).split(''));
  const dfs = (row: number) => {
    if (row === n) { res.push(board.map(r => r.join(''))); return; }
    for (let col = 0; col < n; col++) {
      if (cols.has(col) || diag.has(row - col) || anti.has(row + col)) continue;
      board[row][col] = 'Q';
      cols.add(col); diag.add(row - col); anti.add(row + col);
      dfs(row + 1);
      board[row][col] = '.';
      cols.delete(col); diag.delete(row - col); anti.delete(row + col);
    }
  };
  dfs(0);
  return res;
}

Pruning 101: When to Cut the Branch

• Sorted input + duplicate skipping : skip an element equal to the one before it when choices at the same level repeat.
• Remaining candidates cannot reach target : e.g. in combination-sum with positive numbers, stop when target < nums[i].
• Concurrency checks like N-Queens: reject a placement immediately rather than after recursion.
• Limit the partial-solution size : cut when path.length + remaining < k (a common combinations speedup).

Common Mistakes

• Pushing path instead of [...path] : the array is mutated later, so the stored result changes too.
• Forgetting to undo : without path.pop(), iterations leak choices between branches.
• Not removing dedup : generating [1,2] and [2,1] for combination problems because start was not used.
• Using the same array for permutations without a used set.
• Not calling out exponential complexity : always state 2^n / n! and the pruning that keeps it tractable.

Frequently Asked Questions

Related Tutorials

• Dynamic Programming : memoize overlapping backtracking branches.
• BFS vs DFS : the traversal backbone of every backtracking call.
• Hash Maps : O(1) used/seen tracking during recursion.
• Backtracking practice problems : company-tagged questions.