Subsets - Generating the Power Set | Chinese Powered Labs

Problem Statement #

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output: [
  [],
  [1],
  [2],
  [1,2],
  [3],
  [1,3],
  [2,3],
  [1,2,3]
]

Understanding the Problem #

The power set of a set is the set of all possible subsets, including the empty set and the set itself. For a set with n elements, the power set will contain exactly 2^n subsets. This is because for each element, we have two choices: include it in a subset or exclude it.

For example, with [1,2,3]:

We start with the empty set []
For element 1: we can either include it or not → [], [1]
For element 2: for each existing subset, we can include 2 or not → [], [1], [2], [1,2]
For element 3: same process → all 8 subsets shown above

Solution Approach #

The iterative approach leverages a key insight: when we encounter a new element, we can generate new subsets by taking all existing subsets and appending the new element to each one.

Algorithm Strategy #

Initialize with an empty set [] (since the empty set is always part of the power set)
For each number in the input array:
- Take all currently existing subsets
- Create new subsets by appending the current number to each existing subset
- Add these new subsets to our result array
Return the complete array of subsets

This approach is elegant because it builds the solution incrementally, where each iteration doubles the number of subsets.

Code Implementation #

var subsets = function(nums) {
    // Helper function to add a number to all existing subsets
    function add(arr, num) {
        const fixLength = arr.length;
        
        // Iterate through existing subsets (use fixed length to avoid infinite loop)
        for (let i = 0; i < fixLength; i++) {
            // Create new subset by appending num to existing subset
            arr.push(arr[i].concat(num));
        }
    }
    
    // Initialize result array with empty set
    let arr = [];
    arr.push([]);
    
    // Process each number in input
    for (let i = 0; i < nums.length; i++) {
        add(arr, nums[i]);
    }
    
    return arr;
};

Detailed Code Breakdown #

The Helper Function #

function add(arr, num) {
    const fixLength = arr.length;
    
    for (let i = 0; i < fixLength; i++) {
        arr.push(arr[i].concat(num));
    }
}

Purpose: This function takes an array of subsets and a number, then creates new subsets by appending the number to each existing subset.

Key Points:

We store arr.length in fixLength before the loop starts. This is critical because we’re modifying the array while iterating.
Without fixLength, the loop would run infinitely as we keep adding elements to arr during iteration.
concat(num) creates a new array with num appended, preserving the original subset.

Example Walkthrough:

Let’s say we have:

Current arr = [[], [1], [2], [1,2]]
New number = 3

The function will:

Fix length at 4 (current number of subsets)
For i=0: Take [], append 3 → push [3]
For i=1: Take [1], append 3 → push [1,3]
For i=2: Take [2], append 3 → push [2,3]
For i=3: Take [1,2], append 3 → push [1,2,3]

Result:

arr = [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

The Main Logic #

let arr = [];
arr.push([]);

for (let i = 0; i < nums.length; i++) {
    add(arr, nums[i]);
}

return arr;

Step-by-step execution for nums = [1,2,3]:

Initial State:

arr = [[]]

After processing 1:

arr = [[], [1]]

After processing 2:

arr = [[], [1], [2], [1,2]]

After processing 3:

arr = [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

Complexity Analysis #

Time Complexity: O(n × 2^n)

We generate 2^n subsets
Each subset creation involves array operations (concat)
Overall, we perform proportional work to the size of the output

Space Complexity: O(n × 2^n)

We store 2^n subsets
Each subset can have up to n elements
This is optimal since the output itself requires this much space

Alternative Approaches #

Backtracking Approach #

var subsets = function(nums) {
    const result = [];
    
    function backtrack(start, current) {
        // Add current subset to result
        result.push([...current]);
        
        // Try adding each remaining number
        for (let i = start; i < nums.length; i++) {
            current.push(nums[i]);
            backtrack(i + 1, current);
            current.pop();
        }
    }
    
    backtrack(0, []);
    return result;
};

Bit Manipulation Approach #

var subsets = function(nums) {
    const result = [];
    const n = nums.length;
    const totalSubsets = 1 << n; // 2^n
    
    for (let i = 0; i < totalSubsets; i++) {
        const subset = [];
        for (let j = 0; j < n; j++) {
            // Check if jth bit is set in i
            if (i & (1 << j)) {
                subset.push(nums[j]);
            }
        }
        result.push(subset);
    }
    
    return result;
};

Key Insights #

Pattern Recognition: The iterative approach recognizes that each new element doubles the number of subsets by creating copies with that element included.
Fixed Length Technique: When modifying an array during iteration, storing the initial length prevents infinite loops and ensures we only process original elements.
Building Incrementally: Rather than generating all subsets at once, we build them step by step, which makes the logic clearer and easier to understand.
Immutability: Using concat() instead of push() ensures we don’t modify existing subsets, preserving the correctness of our solution.

Common Pitfalls to Avoid #

Not fixing the array length: If you don’t store arr.length before the loop, you’ll iterate over newly added elements, causing incorrect results or infinite loops.
Modifying existing subsets: Using push() directly on existing subsets will corrupt them. Always create new arrays.
Forgetting the empty set: The empty set is a valid subset and must be included in the result.
Duplicate handling: This solution assumes distinct integers. For arrays with duplicates, you’d need to sort and skip duplicates.

Practice Problems #

Once you understand this problem, try these related challenges:

Subsets II (with duplicates)
Permutations
Combinations
Letter Combinations of a Phone Number
Generate Parentheses

All of these problems use similar backtracking or iterative building techniques.

Conclusion #

The Subsets problem is a fundamental algorithm challenge that teaches important concepts about power sets, iterative building, and careful array manipulation. The iterative solution presented here is intuitive once you recognize the pattern: each element doubles your subset count by creating copies with that element included. Understanding this problem deeply will help you tackle many other combinatorial problems in computer science.