Backtracking Algorithms: From Permutations to N-Queens in TypeScript

Table of Contents

Overview Problem Definition Core Principle: Step-by-Step Illustration Detailed Algorithm Steps TypeScript Implementation 1. Full Permutations 2. Combinations 3. Subsets 4. N-Queens Engineering Optimization: Pruning and State Isolation Applications and Limitations Typical Applications Limitations Summary

838 words

4 minutes

Backtracking Algorithms: From Permutations to N-Queens in TypeScript

2026-04-26

Algorithms

Backtracking

/

TypeScript

/

Algorithms

Overview#

Backtracking is an enumeration method that performs a depth-first search on a decision tree. It tries a choice and continues searching downward; if the current path does not satisfy the conditions, it undoes the choice and returns to the previous level to try other branches.

Prerequisites

DFS: Backtracking is essentially a depth-first traversal of a decision tree

Recursion: Using the call stack to save the choice state at each level

Pruning: Skipping branches that cannot possibly produce an answer

Problem Definition#

Given a set of choice spaces, enumerate all solutions that satisfy the constraints, and avoid invalid branches during the search process.

Element	Description
Input	Candidate elements, target length, target sum, or board constraints
Output	All paths, combinations, permutations, or layouts that satisfy the conditions
Key State	Current path, available range, used markers, constraint checking
Typical Problems	Full permutations, combinations, subsets, combination sum, N-Queens

Core Principle: Step-by-Step Illustration#

Taking the full permutations of [1, 2, 3] as an example, each level selects a number that has not yet been used:

The core actions of backtracking can be broken down into three steps:

Make a choice: Add a candidate element to the current path.
Continue searching: Recurse into the next level of decision-making.
Undo the choice: Restore the state so that the same level can try the next candidate.

If all paths are viewed as a tree, backtracking is “walking all the way down one path, then retreating to switch paths.”

Detailed Algorithm Steps#

1
Algorithm: Backtrack(path, choices)
2
Input: current path path, set of choices choices
3
Output: all solutions that satisfy the conditions
4

5
1. If path already satisfies the termination condition:
6
2.     Copy path to the result set
7
3.     Return
8
4. Iterate over each choice in choices:
9
5.     If choice does not satisfy the constraints, skip
10
6.     Add choice to path
11
7.     Update the selection state
12
8.     Backtrack(path, nextChoices)
13
9.     Undo choice and state update

Complexity Analysis:

Problem Type	Search Scale	Description
Permutations	O(n × n!)	n! permutations, each result copied in O(n)
Combinations	O(k × C(n,k))	Only enumerates paths of length k
Subsets	O(n × 2^n)	Each element is either chosen or not
N-Queens	Approximately O(n!)	After pruning, far less than brute-force n^n
Space Complexity	O(n) + output	Recursion depth and current path are O(n)

TypeScript Implementation#

1. Full Permutations#

1
function permute(nums: number[]): number[][] {
2
  const result: number[][] = [];
3
  const path: number[] = [];
4
  const used = new Array(nums.length).fill(false);
5

6
  function backtrack(): void {
7
    if (path.length === nums.length) {
8
      result.push([...path]);
9
      return;
10
    }
11

12
    for (let i = 0; i < nums.length; i++) {
13
      if (used[i]) continue;
14
      used[i] = true;
15
      path.push(nums[i]);
16
      backtrack();
17
      path.pop();
18
      used[i] = false;
19
    }
20
  }
21

22
  backtrack();
23
  return result;
24
}

2. Combinations#

1
function combine(n: number, k: number): number[][] {
2
  const result: number[][] = [];
3
  const path: number[] = [];
4

5
  function backtrack(start: number): void {
6
    if (path.length === k) {
7
      result.push([...path]);
8
      return;
9
    }
10

11
    for (let i = start; i <= n - (k - path.length) + 1; i++) {
12
      path.push(i);
13
      backtrack(i + 1);
14
      path.pop();
15
    }
16
  }
17

18
  backtrack(1);
19
  return result;
20
}

3. Subsets#

1
function subsets(nums: number[]): number[][] {
2
  const result: number[][] = [];
3
  const path: number[] = [];
4

5
  function backtrack(start: number): void {
6
    result.push([...path]);
7

8
    for (let i = start; i < nums.length; i++) {
9
      path.push(nums[i]);
10
      backtrack(i + 1);
11
      path.pop();
12
    }
13
  }
14

15
  backtrack(0);
16
  return result;
17
}

4. N-Queens#

1
function solveNQueens(n: number): string[][] {
2
  const result: string[][] = [];
3
  const board = Array.from({ length: n }, () => new Array(n).fill('.'));
4
  const cols = new Set<number>();
5
  const diag1 = new Set<number>();
6
  const diag2 = new Set<number>();
7

8
  function backtrack(row: number): void {
9
    if (row === n) {
10
      result.push(board.map(line => line.join('')));
11
      return;
12
    }
13

14
    for (let col = 0; col < n; col++) {
15
      if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) continue;
16
      cols.add(col);
17
      diag1.add(row - col);
18
      diag2.add(row + col);
19
      board[row][col] = 'Q';
20

21
      backtrack(row + 1);
22

23
      board[row][col] = '.';
24
      cols.delete(col);
25
      diag1.delete(row - col);
26
      diag2.delete(row + col);
27
    }
28
  }
29

30
  backtrack(0);
31
  return result;
32
}

Engineering Optimization: Pruning and State Isolation#

The most error-prone aspect of backtracking code is state reuse. In engineering, optimization can be approached from three angles:

Optimization Point	Approach	Value
Pruning conditions upfront	First check whether remaining elements are sufficient and whether the current sum exceeds the limit	Reduces invalid recursion
Paired state modifications	`push` and `pop`, `add` and `delete` appear in pairs	Avoids contaminating other branches
Copy results	Use `[...path]` when collecting answers	Prevents subsequent backtracking from modifying already-saved results

In N-Queens, using the three sets cols / diag1 / diag2 instead of scanning cell by cell reduces each validity check from O(n) to O(1).

Applications and Limitations#

Typical Applications#

Enumeration problems such as permutations, combinations, and subsets
Board search: N-Queens, Sudoku
Path search: maze paths, word search
Constraint satisfaction problems: parenthesis generation, phone number letter combinations

Limitations#

Limitation	Description
Large search space	Most backtracking problems are inherently exponential
Prone to state contamination	Forgetting to undo a choice leads to incorrect results
Limited recursion depth	Excessive depth may trigger call stack limits

Summary#

Key Takeaways:

Backtracking = DFS + state selection + undoing choices.
Permutations use used to control repeated use; combinations and subsets use start to control order.
Pruning does not change the answer; it skips branches that cannot possibly produce an answer.
When collecting results, you must copy the current path and cannot directly save a reference.