Backtracking — Permutations, Combinations, Subsets

0/12 in this phase0/57 across the roadmap

📖 Concept

Backtracking is a systematic way to explore ALL possibilities by building solutions incrementally and abandoning paths that can't lead to valid solutions ("pruning").

Template:

function backtrack(state, choices):
    if (goal reached): record solution
    for each choice in choices:
        if (choice is valid):
            make choice
            backtrack(updated state, remaining choices)
            undo choice  ← THE KEY STEP (backtrack!)

Classic backtracking problems:

Subsets — Generate all 2ⁿ subsets of a set
Permutations — Generate all n! orderings
Combinations — Choose k items from n (nCk)
N-Queens — Place n queens on n×n board with no conflicts
Sudoku solver — Fill grid satisfying all constraints
Word search — Find word in grid following adjacent cells

Key concept — PRUNING: Without pruning, backtracking is brute force. Pruning = skipping branches that can't lead to valid solutions. Good pruning dramatically reduces the search space.

Time complexity: Usually exponential — O(2ⁿ), O(n!), O(nᵏ). But pruning can make it practical.

🏠 Real-world analogy: Solving a maze. At each fork, pick a path. If you hit a dead end, backtrack to the last fork and try the other path. You explore every possibility but avoid revisiting dead ends.

💻 Code Example

codeTap to expand ⛶

1// SUBSETS — Generate all 2ⁿ subsets
2function subsets(nums: number[]): number[][] {
3  const result: number[][] = [];
4  function backtrack(start: number, current: number[]): void {
5    result.push([...current]); // Every state is a valid subset
6    for (let i = start; i < nums.length; i++) {
7      current.push(nums[i]);         // Choose
8      backtrack(i + 1, current);     // Explore
9      current.pop();                  // Undo (backtrack!)
10    }
11  }
12  backtrack(0, []);
13  return result;
14}
15
16// PERMUTATIONS — Generate all n! orderings
17function permutations(nums: number[]): number[][] {
18  const result: number[][] = [];
19  function backtrack(current: number[], remaining: Set<number>): void {
20    if (current.length === nums.length) {
21      result.push([...current]);
22      return;
23    }
24    for (const num of remaining) {
25      current.push(num);
26      remaining.delete(num);
27      backtrack(current, remaining);
28      remaining.add(num);  // Undo
29      current.pop();       // Undo
30    }
31  }
32  backtrack([], new Set(nums));
33  return result;
34}
35
36// COMBINATIONS — Choose k from n
37function combine(n: number, k: number): number[][] {
38  const result: number[][] = [];
39  function backtrack(start: number, current: number[]): void {
40    if (current.length === k) { result.push([...current]); return; }
41    // Pruning: stop if not enough elements left
42    for (let i = start; i <= n - (k - current.length) + 1; i++) {
43      current.push(i);
44      backtrack(i + 1, current);
45      current.pop();
46    }
47  }
48  backtrack(1, []);
49  return result;
50}
51
52// N-QUEENS — Place n queens with no conflicts
53function solveNQueens(n: number): string[][] {
54  const result: string[][] = [];
55  const cols = new Set<number>();
56  const diag1 = new Set<number>(); // row - col
57  const diag2 = new Set<number>(); // row + col
58  const board: string[][] = Array.from({length: n}, () => Array(n).fill('.'));
59
60  function backtrack(row: number): void {
61    if (row === n) { result.push(board.map(r => r.join(''))); return; }
62    for (let col = 0; col < n; col++) {
63      if (cols.has(col) || diag1.has(row-col) || diag2.has(row+col)) continue;
64      // Place queen
65      board[row][col] = 'Q';
66      cols.add(col); diag1.add(row-col); diag2.add(row+col);
67      backtrack(row + 1);
68      // Remove queen (backtrack)
69      board[row][col] = '.';
70      cols.delete(col); diag1.delete(row-col); diag2.delete(row+col);
71    }
72  }
73  backtrack(0);
74  return result;
75}
76
77// WORD SEARCH — Find word in grid
78function exist(board: string[][], word: string): boolean {
79  const rows = board.length, cols = board[0].length;
80  function dfs(r: number, c: number, idx: number): boolean {
81    if (idx === word.length) return true;
82    if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== word[idx]) return false;
83    const temp = board[r][c];
84    board[r][c] = '#'; // Mark visited
85    const found = dfs(r+1,c,idx+1) || dfs(r-1,c,idx+1) || dfs(r,c+1,idx+1) || dfs(r,c-1,idx+1);
86    board[r][c] = temp; // Restore (backtrack!)
87    return found;
88  }
89  for (let r = 0; r < rows; r++)
90    for (let c = 0; c < cols; c++)
91      if (dfs(r, c, 0)) return true;
92  return false;
93}

🏋️ Practice Exercise

Practice Problems (Easy → Hard):

Generate all subsets of a set of unique numbers
Generate all permutations of a set of unique numbers
Generate all combinations of k numbers from [1..n]
Generate all valid parentheses sequences of n pairs
Letter combinations of a phone number (2-9 mapping)
Solve the N-Queens problem
Word search in a 2D grid
Combination sum — find all combos that sum to target (reuse allowed)
Sudoku solver
Partition a string into all possible palindrome partitions

⚠️ Common Mistakes

Forgetting to UNDO the choice (backtrack) — the most common backtracking bug
Not creating a copy when recording solutions — push([...current]) not push(current)
Not pruning — leads to exploring unnecessary branches; always look for ways to skip
Confusing subsets (2ⁿ), permutations (n!), and combinations (nCk)
Modifying global state instead of passing state through parameters

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Backtracking — Permutations, Combinations, Subsets

Was this topic helpful?

← PreviousDivide and Conquer Next →Greedy Algorithms