Power Set

Problem Statement

Given an array of distinct integers, generate all possible subsets (the power set). The power set includes the empty set and the set itself.

Example:

Noob-Friendly Explanation

Imagine you're packing for a trip and you have 3 items: a hat, sunglasses, and a scarf. You want to list every possible combination of items you could bring:

• Bring nothing: []
• Bring just hat: [hat]
• Bring just sunglasses: [sunglasses]
• Bring just scarf: [scarf]
• Bring hat + sunglasses: [hat, sunglasses]
• Bring hat + scarf: [hat, scarf]
• Bring sunglasses + scarf: [sunglasses, scarf]
• Bring all three: [hat, sunglasses, scarf]

That's 8 combinations for 3 items (2³ = 8). This is the power set!

The bit manipulation trick: for 3 items, use numbers 0 to 7 (000 to 111 in binary). Each bit represents whether an item is included (1) or not (0). Number 5 = 101 means include item 0 and item 2 but not item 1.

Approach 1: Brute Force (Recursion / Backtracking)

Intuition

For each element, we have two choices: include it or exclude it. Recursively make this choice for each element.

Algorithm

1. Start with an empty subset
2. For each element, branch into two paths: include it or skip it
3. When we've decided for all elements, add the current subset to the result

import java.util.*;

class Solution {
    public static List<List<Integer>> powerSet(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }

    private static void backtrack(int[] nums, int index, List<Integer> current,
                                   List<List<Integer>> result) {
        // Base case: considered all elements
        if (index == nums.length) {
            result.add(new ArrayList<>(current));
            return;
        }

        // Choice 1: Don't include nums[index]
        backtrack(nums, index + 1, current, result);

        // Choice 2: Include nums[index]
        current.add(nums[index]);
        backtrack(nums, index + 1, current, result);
        current.remove(current.size() - 1); // backtrack
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        List<List<Integer>> result = powerSet(nums);
        for (List<Integer> subset : result) {
            System.out.println(subset);
        }
    }
}

Complexity Analysis

• Time Complexity: O(N * 2^N) — There are 2^N subsets, each takes O(N) to copy
• Space Complexity: O(N * 2^N) — Storing all subsets

Approach 2: Optimal (Bit Manipulation)

Intuition

For an array of N elements, there are 2^N subsets. Each number from 0 to 2^N - 1 represents a unique subset when viewed in binary. The i-th bit tells us whether to include the i-th element.

Example for [1, 2, 3]:

Algorithm

1. Compute total = 2^N (use 1 << n)
2. For each number i from 0 to total - 1:
   • Check each bit of i
   • If bit j is set, include nums[j] in the subset
3. Add the subset to result

import java.util.*;

class Solution {
    public static List<List<Integer>> powerSet(int[] nums) {
        int n = nums.length;
        int total = 1 << n; // 2^n
        List<List<Integer>> result = new ArrayList<>();

        for (int mask = 0; mask < total; mask++) {
            List<Integer> subset = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                // Check if j-th bit is set in mask
                if ((mask & (1 << j)) != 0) {
                    subset.add(nums[j]);
                }
            }
            result.add(subset);
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        List<List<Integer>> result = powerSet(nums);
        for (List<Integer> subset : result) {
            System.out.println(subset);
        }
        // []
        // [1]
        // [2]
        // [1, 2]
        // [3]
        // [1, 3]
        // [2, 3]
        // [1, 2, 3]
    }
}

Complexity Analysis

• Time Complexity: O(N * 2^N) — 2^N subsets, each taking O(N) to generate
• Space Complexity: O(N * 2^N) — Storing all subsets

Key Takeaways

1. 2^N Subsets: An array of N elements always has exactly 2^N subsets
2. Bit Masking: Each number from 0 to 2^N-1 represents a unique subset
3. Check Bit j: (mask & (1 << j)) != 0 tells if element j is in the subset
4. Both Approaches Same Complexity: Recursion and bit manipulation have the same time/space complexity, but bit manipulation is iterative and often cleaner
5. Limitation: Bit manipulation works for N ≤ 30 (since 2^30 ≈ 10^9). For larger N, neither approach is feasible