Subsets Generation Using Bitmask in DSA Python

Mental Model

Each subset can be represented by a series of on/off switches, where each switch decides if an element is included or not.

Analogy: Imagine you have a row of light switches, each controlling a lamp. Turning a switch on means including that lamp in the room's lighting; off means excluding it. Every combination of on/off switches creates a unique lighting setup, just like every combination of elements forms a subset.

Set: [a, b, c]
Bitmask positions: 0 1 2
Example bitmask: 101
Subset: [a, c]

Positions:
[a] ← bit 0
[b] ← bit 1
[c] ← bit 2

Dry Run Walkthrough

Input: set: [1, 2, 3]

Goal: Generate all subsets of [1, 2, 3] using bitmask representation

Step 1: Start with bitmask 000 (decimal 0), no elements included

bitmask=000 -> subset=[]

Why: This represents the empty subset with no elements selected

Step 2: Bitmask 001 (decimal 1), include element at position 0

bitmask=001 -> subset=[1]

Why: The last bit is on, so include the first element

Step 3: Bitmask 010 (decimal 2), include element at position 1

bitmask=010 -> subset=[2]

Why: The middle bit is on, so include the second element

Step 4: Bitmask 011 (decimal 3), include elements at positions 0 and 1

bitmask=011 -> subset=[1, 2]

Why: Last two bits are on, so include first and second elements

Step 5: Bitmask 100 (decimal 4), include element at position 2

bitmask=100 -> subset=[3]

Why: The first bit is on, so include the third element

Step 6: Bitmask 101 (decimal 5), include elements at positions 0 and 2

bitmask=101 -> subset=[1, 3]

Why: Bits at positions 0 and 2 are on, include first and third elements

Step 7: Bitmask 110 (decimal 6), include elements at positions 1 and 2

bitmask=110 -> subset=[2, 3]

Why: Bits at positions 1 and 2 are on, include second and third elements

Step 8: Bitmask 111 (decimal 7), include all elements

bitmask=111 -> subset=[1, 2, 3]

Why: All bits are on, so include all elements

Result:

All subsets generated:
[]
[1]
[2]
[1, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]

Annotated Code

DSA Python

class SubsetsBitmask:
    def __init__(self, nums):
        self.nums = nums

    def generate_subsets(self):
        n = len(self.nums)
        total_subsets = 1 << n  # 2^n subsets
        result = []
        for bitmask in range(total_subsets):
            subset = []
            for i in range(n):
                if bitmask & (1 << i):
                    subset.append(self.nums[i])
            result.append(subset)
        return result


if __name__ == '__main__':
    nums = [1, 2, 3]
    subsets_generator = SubsetsBitmask(nums)
    subsets = subsets_generator.generate_subsets()
    for subset in subsets:
        print(subset)

total_subsets = 1 << n # 2^n subsets

Calculate total number of subsets as 2 to the power of n

for bitmask in range(total_subsets):

Iterate over all bitmasks from 0 to 2^n - 1 to represent all subsets

for i in range(n):

Check each bit position to decide if element at i is included

if bitmask & (1 << i):

Check if the i-th bit in bitmask is set (1) to include element

subset.append(self.nums[i])

Add element to current subset if bit is set

result.append(subset)

Add the formed subset to the result list

Output

[]

[1]

[2]

[1, 2]

[3]

[1, 3]

[2, 3]

[1, 2, 3]

Complexity Analysis

Time: O(n * 2^n) because we generate 2^n subsets and for each subset we check n bits

Space: O(n * 2^n) because we store all subsets and each subset can have up to n elements

vs Alternative: Compared to recursive backtracking, bitmask is iterative and often simpler to implement but both have similar time and space complexity

Edge Cases

empty input list

Returns one subset: the empty subset []

DSA Python

total_subsets = 1 << n  # 2^n subsets

single element list

Returns two subsets: [] and [element]

DSA Python

for bitmask in range(total_subsets):

When to Use This Pattern

When you need to generate all subsets of a set and want a simple, direct way to represent inclusion/exclusion, use bitmasking because each bit naturally maps to an element's presence.

Common Mistakes

Mistake: Not using bit shifts correctly to check bits, causing wrong subsets
Fix: Use (bitmask & (1 << i)) to check if the i-th bit is set

Mistake: Looping bitmask from 1 to 2^n instead of 0 to 2^n - 1, missing empty subset
Fix: Start bitmask from 0 to include the empty subset

Summary

Generates all subsets of a set by using bits to represent element inclusion.

Use when you want a clear, iterative way to list every subset of a small set.

Each bit in a number acts like a switch deciding if an element is in the subset.