Power Set with Bit Manipulation

Explanation & Solution

Description

Given an array nums of distinct integers, return all possible subsets (the power set) using bitwise operations.

Use bit manipulation to iterate through all possible inclusion/exclusion combinations. Each integer from 0 to 2^n - 1 represents a unique subset, where each bit indicates whether the corresponding element is included.

The solution set must not contain duplicate subsets. Return the subsets in any order.

Input:nums = [1,2,3]

Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Explanation: There are 2^3 = 8 subsets. Each number from 0 to 7 in binary maps to a subset: 000→[], 001→[1], 010→[2], 011→[1,2], 100→[3], 101→[1,3], 110→[2,3], 111→[1,2,3].

Constraints

1 <= nums.length <= 10
-10 <= nums[i] <= 10
All elements of nums are unique.

Approach

Subsets pattern

1. Determine the Total Number of Subsets

For an array of n elements, there are exactly 2^n possible subsets.
Compute this as 1 << n (left-shift 1 by n positions).

2. Iterate Through All Bitmasks

Loop through every integer mask from 0 to 2^n - 1.
Each mask represents one unique subset.
In binary, each bit position corresponds to an element in nums.

3. Build Each Subset from the Bitmask

For each mask, iterate through bit positions 0 to n-1.
If mask & (1 << i) is non-zero, the i-th element is included in this subset.
Push nums[i] into the current subset array.

4. Collect All Subsets

After building a subset from the current mask, push it into the result array.
After all masks are processed, result contains all 2^n subsets.

5. Return the Result

Return the result array containing every possible subset.

Key Insight

Each integer from 0 to 2^n - 1 has a unique binary representation that naturally maps to a subset — bit i being 1 means "include element i".
This gives a clean iterative solution with no recursion needed.

Time

O(n * 2^n)for each of the 2^n masks, we check n bits.

Space

O(n * 2^n) to store all subsets.

Visualization

Input:

[1, 2, 3]

—

No animation available

Left (L)Right (R)ConvergedDone

0 steps

Solution Code

Target Sum

Increasing Subsequences