Bit Manipulation / UsageSubset via BitsMedium

Subset via Bits — Generate All 2^N Subsets

Use bitmask 0 to 2^N-1 to enumerate every possible subset. Each bit decides include or exclude.

LC
Practice on LeetCode 78: Subsets
Open Problem

What does it solve?

Generate all 2^N subsets of a set. Each integer from 0 to 2^N-1 acts as a bitmask: if bit j is set, element j is included. No recursion needed.

The Pattern

for mask = 0 to (1 << n) - 1:
  for j = 0 to n-1:
    if mask & (1 << j):
      include arr[j]
Interactive Visualization
Included
Bitmask 1
Current Subset
Elements
Bitmask (0)
{ }
All subsets found
Step 0 of 0
Mask
0
Subset Size
0
Found
0
Total (2^N)
0
Ready. Press Play or Next to generate all subsets.
✓ All Found
Speed
C++ — Subsets via Bitmask
vector<vector<int>> subsets(vector<int>& nums) {
    int n = nums.size();
    vector<vector<int>> result;

    for (int mask = 0; mask < (1 << n); mask++) {
        vector<int> subset;
        for (int j = 0; j < n; j++) {
            if (mask & (1 << j))
                subset.push_back(nums[j]);
        }
        result.push_back(subset);
    }
    return result;
}
Complexity
Time
O(N × 2^N)

2^N subsets, N bits to check per subset.

Space
O(N × 2^N)

Storing all subsets.

📝 Notes

▼