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.