Generate All Permutations
Generate all possible arrangements (permutations) of n distinct elements. For n elements, there are exactly n! permutations. This classic backtracking problem demonstrates recursive exploration of the solution space, where we systematically build permutations by choosing elements and backtracking when complete. Used in combinatorics, constraint satisfaction, and optimization problems.
Visualization
Interactive visualization for Generate All Permutations
Interactive visualization with step-by-step execution
Implementation
1function permute(nums: number[]): number[][] {
2 const result: number[][] = [];
3 const current: number[] = [];
4 const used: boolean[] = Array(nums.length).fill(false);
5
6 function backtrack(): void {
7 if (current.length === nums.length) {
8 result.push([...current]);
9 return;
10 }
11
12 for (let i = 0; i < nums.length; i++) {
13 if (used[i]) continue;
14
15 current.push(nums[i]);
16 used[i] = true;
17 backtrack();
18 used[i] = false;
19 current.pop();
20 }
21 }
22
23 backtrack();
24 return result;
25}
26
27// Swap-based approach (Heap's algorithm)
28function permuteSwap(nums: number[]): number[][] {
29 const result: number[][] = [];
30
31 function backtrack(start: number): void {
32 if (start === nums.length) {
33 result.push([...nums]);
34 return;
35 }
36
37 for (let i = start; i < nums.length; i++) {
38 [nums[start], nums[i]] = [nums[i], nums[start]];
39 backtrack(start + 1);
40 [nums[start], nums[i]] = [nums[i], nums[start]];
41 }
42 }
43
44 backtrack(0);
45 return result;
46}Deep Dive
Theoretical Foundation
Permutation generation uses backtracking to explore all orderings. For each position, we try every unused element, recursively permute remaining elements, then backtrack by unmarking the element. Time: O(n!) to generate n! permutations, O(n) to copy each permutation, total O(n! × n). Space: O(n) recursion depth + O(n) for tracking used elements. Alternative: Heap's algorithm uses swaps instead of used array, generating permutations in place with O(1) extra space.
Complexity
Time
O(n! × n)
O(n! × n)
O(n! × n)
Space
O(n! × n) output + O(n) recursion
Applications
Industry Use
Traveling Salesman Problem (exploring all routes)
Scheduling problems (task ordering)
Anagram generation
Combinatorial optimization
Cryptographic attacks (brute force)
DNA sequence analysis
Game AI (exploring move sequences)
Use Cases
Related Algorithms
Tower of Hanoi
Tower of Hanoi is a classic mathematical puzzle invented by French mathematician Édouard Lucas in 1883. The puzzle consists of three rods and n disks of different sizes that can slide onto any rod. The objective is to move the entire stack from one rod to another, following rules: (1) only one disk can be moved at a time, (2) only the top disk from any rod can be moved, (3) a larger disk cannot be placed on a smaller disk. The elegant recursive solution requires exactly 2^n - 1 moves.
Generate All Combinations
Generate all C(n,k) combinations - all possible selections of k elements from n elements where order doesn't matter. Unlike permutations, {1,2,3} and {3,2,1} are the same combination. Uses backtracking to explore choices systematically, ensuring each combination is counted once. Fundamental in statistics, probability, lottery systems, and feature selection in machine learning.
Generate All Subsets (Power Set)
Generate the power set - all 2^n possible subsets of an n-element set, including the empty set and the set itself. For example, subsets of {1,2,3} are: {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}. Can be elegantly solved using recursion, iteration, or bit manipulation. Essential in combinatorial optimization and constraint satisfaction.
Quicksort
A highly efficient, in-place sorting algorithm that uses divide-and-conquer strategy. Invented by Tony Hoare in 1959, it remains one of the most widely used sorting algorithms due to its excellent average-case performance and cache efficiency.