Subsets Generation Using Bitmask in DSA Python - Execution Trace

Concept Flow - Subsets Generation Using Bitmask

Start with input set

↓

Calculate total subsets = 2^n

↓

For each number from 0 to 2^n - 1

↓

Use bits of number as mask

↓

If bit j is 1, include element j

↓

Form subset

↓

Add subset to result

↓

Repeat for all numbers

↓

Return all subsets

We generate all subsets by counting from 0 to 2^n - 1 and using each number's bits to decide which elements to include.

Execution Sample

DSA Python

nums = ['a', 'b', 'c']
for mask in range(8):
  subset = []
  for j in range(3):
    if mask & (1 << j):
      subset.append(nums[j])
  print(subset)

This code prints all subsets of [a, b, c] by using bitmask from 0 to 7.

Execution Table

Step	Operation	Mask (binary)	Included Elements	Subset Formed	Visual State
1	mask=0	000	none	[]	[]
2	mask=1	001	a	[a]	[] [a]
3	mask=2	010	b	[b]	[] [a] [b]
4	mask=3	011	a, b	[a, b]	[] [a] [b] [a, b]
5	mask=4	100	c	[c]	[] [a] [b] [a, b] [c]
6	mask=5	101	a, c	[a, c]	[] [a] [b] [a, b] [c] [a, c]
7	mask=6	110	b, c	[b, c]	[] [a] [b] [a, b] [c] [a, c] [b, c]
8	mask=7	111	a, b, c	[a, b, c]	[] [a] [b] [a, b] [c] [a, c] [b, c] [a, b, c]
9	End	-	-	-	All subsets generated

💡 mask reaches 7 (2^3 - 1), all subsets generated

Variable Tracker

Variable	Start	After mask=0	After mask=1	After mask=2	After mask=3	After mask=4	After mask=5	After mask=6	After mask=7	Final
mask	N/A	0	1	2	3	4	5	6	7	End
subset	[]	[]	[a]	[b]	[a, b]	[c]	[a, c]	[b, c]	[a, b, c]	All subsets formed
Included Elements	N/A	none	a	b	a, b	c	a, c	b, c	a, b, c	N/A

Key Moments - 3 Insights

Why do we use 2^n as the total number of subsets?

Because each element can be either included or excluded, so total subsets = 2 choices per element multiplied n times = 2^n. See execution_table steps 1 to 8.

How does the bitmask decide which elements to include?

Each bit in the mask corresponds to an element index. If bit j is 1, element j is included. This is shown in execution_table column 'Mask (binary)' and 'Included Elements'.

Why do we start mask from 0?

Mask 0 means no bits set, so empty subset. This ensures we include the empty subset as part of all subsets. See execution_table step 1.

Visual Quiz - 3 Questions

Look at the execution_table, what subset is formed at step 6 when mask=5?

A [a, c]

B [b, c]

C [a, b]

D [c]

💡 Hint

Check the 'Subset Formed' column at step 6 in execution_table.

At which step does the subset include all elements a, b, and c?

A Step 4

B Step 8

C Step 2

D Step 1

💡 Hint

Look for '[a, b, c]' in the 'Subset Formed' column in execution_table.

If the input set had 4 elements, how many subsets would the bitmask loop run?

A 8

B 4

C 16

D 32

💡 Hint

Recall total subsets = 2^n, so for n=4, total subsets = 2^4.

Concept Snapshot

Subsets Generation Using Bitmask:
- Total subsets = 2^n for n elements
- Loop mask from 0 to 2^n - 1
- Use bits of mask to include elements
- Bit j = 1 means include element j
- Includes empty subset (mask=0)
- Efficient way to generate all subsets

Full Transcript

We generate all subsets of a set by using a bitmask from 0 to 2^n - 1, where n is the number of elements. Each bit in the mask represents whether to include the corresponding element. For example, mask 5 (binary 101) includes elements at positions 0 and 2. We loop through all masks, form subsets accordingly, and collect them. This method covers all subsets including the empty one. The total number of subsets is 2^n because each element has two choices: include or exclude. This approach is efficient and easy to implement.

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