L4. Power Set | Bit Manipulation

1. Why Do We Need This? (Problem Statement & Status Quo)

When working with arrays or sets in computer science, a frequent requirement is generating all possible subsets—collectively known as the Power Set.

Given an array of numbers (nums), our task is to return a list of all possible subsets (including the empty set and the full set). For example, given nums = [1, 2, 3], the total number of subsets is $8$.

While a recursive approach (backtracking) can solve this problem, bit manipulation offers an iterative, highly efficient alternative that completely eliminates recursive stack overhead.

2. Core Mental Model & Analogy

Real-Life Analogy: The Light Switches

Imagine you are packing for a trip and you have three items on a table:

1. Item 0: Jacket ($1$)
2. Item 1: Umbrella ($2$)
3. Item 2: Sunglasses ($3$)

Above each item sits a light switch that can be either OFF (0) or ON (1).

• If the switch is OFF (0), you do not take the item.
• If the switch is ON (1), you take the item.

As you flip the switches through every possible binary combination from 000 to 111, you produce every unique luggage combination (subset) possible. With $3$ items, there are $2^3 = 8$ unique combinations of switch states.

3. Naive vs. Better Approach

• Recursive / Backtracking Approach: Explores subsets by deciding whether to include or exclude each element branch-by-branch. While intuitive, it incurs implicit memory overhead due to the recursion call stack.
• Bit Manipulation Approach: Treats the problem as counting from $0$ to $2^n - 1$. Each integer's binary representation directly dictates whether array elements are included. It requires no recursion, runs iteratively, and uses straightforward bitwise operators.

4. Step-by-Step Evolution: Determining Total Subsets via Bitwise Shift

If an array contains $n$ elements, the total number of subsets is always $2^n$. In bit manipulation, we calculate $2^n$ instantly using the Left Shift Operator (<<):

Why does this work?

• If $n = 1$, $1 \ll 1 = 2^1 = 2$ subsets.
• If $n = 2$, $1 \ll 2 = 2^2 = 4$ subsets.
• If $n = 3$, $1 \ll 3 = 2^3 = 8$ subsets.
• If $n = 4$, $1 \ll 4 = 2^4 = 16$ subsets.

5. Visualizing the Binary Matrix for nums = [1, 2, 3]

For $n = 3$, we iterate our number counter from decimal 0 to 7 (000 to 111 in binary). Each bit position corresponds to an index in our nums array (Index 0, Index 1, Index 2).

6. Checking If a Bit Is Set

To check if the $i^{\text{th}}$ bit of our loop number is set (1), we use the bitwise AND operator combined with a left shift:

• If the result is a non-zero number, the bit is set (1), meaning we include nums[i] in our current subset.
• If the result is 0, the bit is not set, meaning we skip nums[i].

7. Complete Flow Walkthrough

Let's trace how our algorithm executes step-by-step for nums = [1, 2, 3]:

8. Pseudo-Code Implementation

Function generateSubsets(nums):
    n = length of nums
    subsetsCount = 1 << n  // Equivalent to 2^n
    answer = []

    // Loop through every possible binary combination from 0 to 2^n - 1
    For num = 0 to subsetsCount - 1:
        currentSubset = []
        
        // Check each bit position from 0 to n - 1
        For i = 0 to n - 1:
            // If the i-th bit is set in 'num'
            If (num & (1 << i)) != 0:
                Add nums[i] to currentSubset
                
        // Add the generated subset to our master list
        Add currentSubset to answer

    Return answer

9. Complexity Analysis

Time Complexity: $\mathcal{O}(n \times 2^n)$

• Outer Loop: Runs $2^n$ times (once for every subset).
• Inner Loop: Runs $n$ times (checking each of the $n$ bits).
• Total Time: Multiplying the outer loop iterations by the inner loop checks gives $\mathcal{O}(n \times 2^n)$.

Space Complexity: $\mathcal{O}(n \times 2^n)$ auxiliary space (excluding output storage)

• There are $2^n$ total subsets generated.
• The average length of these subsets is proportional to $n$, meaning the total storage required to hold all elements across all subsets scales around $\mathcal{O}(n \times 2^n)$. Note that recursive approaches carry an additional $\mathcal{O}(n)$ call-stack memory overhead, which this iterative bit manipulation approach avoids.

10. Summary and Key Takeaways

• Bitwise Power Set Paradigm: The power set problem can be seamlessly solved by mapping binary numbers from $0$ to $2^n - 1$ to subset inclusion states.
• Fast Exponential Calculation: $2^n$ is efficiently computed using the left-shift bitwise operator: 1 << n.
• Bit-Checking Formula: Use (num & (1 << i)) to determine whether the $i^{\text{th}}$ element of the array should be included in the current subset.
• Zero Take vs. One Take: Bit value 0 signifies "do not take" the element, while bit value 1 signifies "take" the element.
• Iterative Advantage: Unlike backtracking recursion, the bit manipulation technique executes iteratively, bypassing recursion stack limits.
• Complexity Tradeoff: Generates all subsets in $\mathcal{O}(n \times 2^n)$ time while cleanly storing the resulting combinations.