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.
Visualization
Interactive visualization for Generate All Subsets (Power Set)
Interactive visualization with step-by-step execution
Implementation
1function subsets(nums: number[]): number[][] {
2 const result: number[][] = [];
3 const current: number[] = [];
4
5 function backtrack(start: number): void {
6 result.push([...current]);
7
8 for (let i = start; i < nums.length; i++) {
9 current.push(nums[i]);
10 backtrack(i + 1);
11 current.pop();
12 }
13 }
14
15 backtrack(0);
16 return result;
17}
18
19// Iterative approach
20function subsetsIterative(nums: number[]): number[][] {
21 const result: number[][] = [[]];
22
23 for (const num of nums) {
24 const newSubsets = result.map(subset => [...subset, num]);
25 result.push(...newSubsets);
26 }
27
28 return result;
29}
30
31// Bit manipulation approach
32function subsetsBitwise(nums: number[]): number[][] {
33 const result: number[][] = [];
34 const n = nums.length;
35 const totalSubsets = 1 << n; // 2^n
36
37 for (let mask = 0; mask < totalSubsets; mask++) {
38 const subset: number[] = [];
39 for (let i = 0; i < n; i++) {
40 if (mask & (1 << i)) {
41 subset.push(nums[i]);
42 }
43 }
44 result.push(subset);
45 }
46
47 return result;
48}Deep Dive
Theoretical Foundation
Power set generation explores a binary choice tree: for each element, either include it or exclude it from the subset. Three elegant approaches: (1) Backtracking: at each position, add current subset to results, then try including each remaining element. (2) Iterative: start with empty set, for each element, add it to all existing subsets. (3) Bit manipulation: use binary numbers 0 to 2^n-1, where each bit represents whether to include element i. All have Time: O(2^n × n), Space: O(n) recursion or O(1) for iterative.
Complexity
Time
O(2^n × n)
O(2^n × n)
O(2^n × n)
Space
O(2^n × n)
Applications
Industry Use
Subset sum problem (0/1 knapsack brute force)
Feature selection in machine learning
Genetic algorithms (chromosome representation)
Set cover problems
Itemset mining in data mining
Generating test cases
Boolean function truth tables
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 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.
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.
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.