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.

Practice

1. What does the bitmask technique help to generate when applied to a set of elements?

easy

A. Only subsets with odd number of elements

B. Only the largest subset of the set

C. Only subsets with even number of elements

D. All possible subsets of the set

Solution

1. Step 1: Understand bitmask representation

   Each bit in a bitmask represents whether an element is included (1) or excluded (0) in a subset.

2. Step 2: Generate subsets using bitmask

   By iterating from 0 to 2^n - 1 (where n is number of elements), all combinations of included/excluded elements are covered, producing all subsets.

3. Final Answer:

   All possible subsets of the set -> Option D

4. Quick Check:

   Bitmask = subsets generator [OK]

Hint: Bitmask bits map directly to subset inclusion [OK]

Common Mistakes:

• Thinking bitmask generates only large subsets
• Confusing bitmask with sorting or filtering
• Assuming bitmask generates only even or odd subsets

2. Which of the following is the correct Python syntax to iterate over all bitmasks for a set of size n?

easy

A. for mask in range(1 << n):

B. for mask in range(n << 1):

C. for mask in range(2 * n):

D. for mask in range(n ** 2):

Solution

1. Step 1: Understand bit shift for 2^n

   Using 1 << n shifts 1 left by n bits, which equals 2 to the power n.

2. Step 2: Use range to cover all bitmasks

   Iterating from 0 to 1 << n - 1 covers all subsets represented by bitmasks.

3. Final Answer:

   for mask in range(1 << n): -> Option A

4. Quick Check:

   1 << n = 2^n range [OK]

Hint: Use 1 << n for 2^n subsets [OK]

Common Mistakes:

• Using multiplication instead of bit shift
• Using n squared or doubled incorrectly
• Confusing range limits

3. What is the output of the following code?

arr = ["a", "b"]
subsets = []
for mask in range(1 << len(arr)):
    subset = []
    for i in range(len(arr)):
        if mask & (1 << i):
            subset.append(arr[i])
    subsets.append(subset)
print(subsets)

medium

A. [['a', 'b'], ['a'], ['b'], []]

B. [[], ['a'], ['b'], ['a', 'b']]

C. [[], ['b'], ['a'], ['b', 'a']]

D. [['a'], ['b'], ['a', 'b'], []]

Solution

1. Step 1: Understand bitmask iteration

   For arr of length 2, masks go from 0 to 3 (00, 01, 10, 11 in binary).

2. Step 2: Map bits to elements

   Mask 0 (00) -> no elements -> [] Mask 1 (01) -> include arr[0] -> ['a'] Mask 2 (10) -> include arr[1] -> ['b'] Mask 3 (11) -> include arr[0], arr[1] -> ['a', 'b']

3. Final Answer:

   [[], ['a'], ['b'], ['a', 'b']] -> Option B

4. Quick Check:

   Bitmask subsets match output [OK]

Hint: Trace bitmask bits to elements included [OK]

Common Mistakes:

• Mixing order of subsets
• Appending elements incorrectly
• Confusing bit positions

4. Identify the error in the following code snippet for generating subsets using bitmask:

arr = [1, 2, 3]
subsets = []
for mask in range(1 << len(arr)):
    subset = []
    for i in range(len(arr)):
        if mask & i:
            subset.append(arr[i])
    subsets.append(subset)
print(subsets)

medium

A. The subset list should be initialized outside the loop

B. The range should be 'range(len(arr))' instead of 'range(1 << len(arr))'

C. The condition should be 'mask & (1 << i)' instead of 'mask & i'

D. The print statement should be inside the inner loop

Solution

1. Step 1: Analyze bitmask condition

   The condition 'mask & i' incorrectly checks bits; it should check if the i-th bit is set using 'mask & (1 << i)'.

2. Step 2: Correct bit checking

   Using 'mask & (1 << i)' correctly tests if the bit at position i is 1, indicating inclusion of arr[i].

3. Final Answer:

   The condition should be 'mask & (1 << i)' instead of 'mask & i' -> Option C

4. Quick Check:

   Bit check needs shift [OK]

Hint: Use bit shift to check bits, not index alone [OK]

Common Mistakes:

• Using 'mask & i' instead of 'mask & (1 << i)'
• Initializing subset outside loop causing accumulation
• Misplacing print inside loops

5. Given a list arr = [1, 2, 2], what is the output of the following code that generates subsets using bitmask?

arr = [1, 2, 2]
subsets = []
for mask in range(1 << len(arr)):
    subset = []
    for i in range(len(arr)):
        if mask & (1 << i):
            subset.append(arr[i])
    subsets.append(subset)
print(subsets)

hard

A. [[], [1], [2], [1, 2], [2], [1, 2], [2, 2], [1, 2, 2]]

B. [[], [1], [2], [2], [1, 2], [1, 2], [2, 2], [1, 2, 2]]

C. [[], [1], [2], [1, 2], [2, 2], [1, 2, 2]]

D. [[], [1], [2], [1, 2], [2, 2], [1, 2, 2], [2]]

Solution

1. Step 1: Calculate total subsets

   For 3 elements, total subsets = 2^3 = 8, masks from 0 to 7.

2. Step 2: Map each mask to subset

   Mask 0 (000): [] Mask 1 (001): [1] Mask 2 (010): [2] (second element) Mask 3 (011): [1, 2] Mask 4 (100): [2] (third element) Mask 5 (101): [1, 2] Mask 6 (110): [2, 2] Mask 7 (111): [1, 2, 2]

3. Final Answer:

   [[], [1], [2], [1, 2], [2], [1, 2], [2, 2], [1, 2, 2]] -> Option A

4. Quick Check:

   Duplicates appear as separate elements [OK]

Hint: Duplicates create repeated subsets with same elements [OK]

Common Mistakes:

• Assuming duplicates merge subsets
• Missing subsets with repeated elements
• Incorrect mask to subset mapping