Subsets Generation Using Bitmask in DSA C# - 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

↓

For each bit position

↓

If bit is 1, include element

↓

Add formed subset to result

↓

Repeat until all subsets generated

↓

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 C#

int n = 3;
int total = 1 << n;
for (int mask = 0; mask < total; mask++) {
  List<int> subset = new List<int>();
  for (int i = 0; i < n; i++) {
    if ((mask & (1 << i)) != 0) subset.Add(i);
  }
}

This code generates all subsets of {0,1,2} by using bitmask from 0 to 7.

Execution Table

Step	Mask (binary)	Operation	Included Elements	Subset Formed
1	000	Check bits 0,1,2	None	[]
2	001	Bit 0 set → include element 0	[0]	[0]
3	010	Bit 1 set → include element 1	[1]	[1]
4	011	Bits 0,1 set → include elements 0,1	[0,1]	[0,1]
5	100	Bit 2 set → include element 2	[2]	[2]
6	101	Bits 0,2 set → include elements 0,2	[0,2]	[0,2]
7	110	Bits 1,2 set → include elements 1,2	[1,2]	[1,2]
8	111	Bits 0,1,2 set → include elements 0,1,2	[0,1,2]	[0,1,2]

💡 All masks from 0 to 7 processed, generating all 8 subsets.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
mask	0	1	2	3	4	5	6	7	7	7
subset	[]	[]	[0]	[1]	[0,1]	[2]	[0,2]	[1,2]	[0,1,2]	[0,1,2]

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 ^ n elements = 2^n. This is shown in execution_table rows where mask goes from 0 to 7 for n=3.

How does the bitmask decide which elements to include?

Each bit in the mask corresponds to an element index. If the bit is 1, that element is included. For example, in step 6 mask 101 binary includes elements 0 and 2, as shown in execution_table.

Why do we check bits using (mask & (1 << i)) != 0?

This expression isolates the bit at position i. If it is 1, the result is not zero, meaning the element at index i should be included. This is the core check in the inner loop of the code.

Visual Quiz - 3 Questions

Look at the execution_table, what subset is formed at step 4?

A [0,1]

B [1,2]

C [0,2]

D []

💡 Hint

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

At which step does the mask include elements 1 and 2 but not 0?

A Step 5

B Step 7

C Step 6

D Step 3

💡 Hint

Look for mask with bits 1 and 2 set but bit 0 unset in the 'Mask (binary)' column.

If n was 4, how many total subsets would the code generate?

A 8

B 12

C 16

D 4

💡 Hint

Recall total subsets = 2^n, so for n=4, check the 'Concept Flow' description.

Concept Snapshot

Subsets Generation Using Bitmask:
- Total subsets = 2^n
- Iterate mask from 0 to 2^n - 1
- For each bit in mask:
  - If bit is 1, include element
- Collect subsets in list
- Efficient way to generate all subsets

Full Transcript

This concept shows how to generate all subsets of a set using bitmasking. We count from 0 to 2^n - 1, where n is the number of elements. Each number's binary form acts as a mask: if a bit is 1, the corresponding element is included in the subset. The code loops through each mask and checks each bit to build subsets. The execution table traces each mask and the subset formed. This method efficiently lists all subsets without recursion.

Practice

1. For an array of 3 elements, which bitmask (decimal) represents the subset containing only the first and third elements?

easy

A. 3

B. 5

C. 6

D. 7

Solution

1. Step 1: Bit assignments

   Bit 0 (rightmost) → element 0 (first). Bit 1 → element 1. Bit 2 → element 2 (third).

2. Step 2: Subset {element 0, element 2}

   Bit 0 = 1, bit 1 = 0, bit 2 = 1. Binary: 101. Decimal: 4+0+1 = 5.

3. Final Answer:

   5 (binary 101) -> Option B

4. Quick Check:

   First element = bit 0, third = bit 2. 101 in binary = 5. [OK]

Hint: Bit 0=first, bit 1=second, bit 2=third. {first,third}=101=5. [OK]

Common Mistakes:

• Using bit 1=first instead of bit 0=first
• Getting 6 (binary 110 = second+third)
• Getting 3 (binary 011 = first+second)

2. In C#, which expression correctly checks if bit j is set in integer mask?

medium

A. (mask | (1 << j)) != 0

B. (mask ^ (1 << j)) > 0

C. (mask & (1 << j)) != 0

D. (mask >> j) == 1

Solution

1. Step 1: AND isolates a bit

   (mask & (1 << j)) keeps only bit j from mask. If bit j was set, result is non-zero (true). If not set, result is 0 (false).

2. Step 2: Why others fail

   OR always sets bit j → always non-zero → always true. XOR flips bit j → non-zero whether set or not. >> j == 1 fails if higher bits are also set.

3. Final Answer:

   (mask & (1 << j)) != 0 -> Option C

4. Quick Check:

   AND isolates. OR sets. XOR flips. Use & to check a bit. [OK]

Hint: Bit check = AND: (mask & (1<

Common Mistakes:

• Using | which always returns non-zero
• Using >> j == 1 which fails with higher set bits
• Using ^ which gives non-zero for both set and unset bits

3. For nums = [1, 2, 3] with n=3, what does mask = 5 (binary 101) represent as a subset?

medium

A. {2, 3}

B. {1, 2}

C. {1, 3}

D. {1, 2, 3}

Solution

1. Step 1: Decode binary 101

   Bit 0 = 1 → include nums[0] = 1. Bit 1 = 0 → exclude nums[1] = 2. Bit 2 = 1 → include nums[2] = 3.

2. Step 2: Result

   Subset = {1, 3}.

3. Final Answer:

   {1, 3} -> Option C

4. Quick Check:

   101: bits 0 and 2 set → nums[0]=1 and nums[2]=3 → {1,3}. [OK]

Hint: Read bits right to left: bit 0=nums[0], bit 1=nums[1], bit 2=nums[2]. 101 → {1,3}. [OK]

Common Mistakes:

• Reading bits left-to-right and getting {3,1}
• Getting {2,3} by reading bit positions wrong
• Including all elements because mask≠0

4. What is the correct outer loop range to generate all subsets of an n-element array using bitmask in C#?

medium

A. for (int mask = 1; mask <= (1 << n); mask++)

B. for (int mask = 0; mask < (1 << n); mask++)

C. for (int mask = 0; mask <= n; mask++)

D. for (int mask = 1; mask < n; mask++)

Solution

1. Step 1: Range needed

   With n elements, bitmasks 0 through 2^n-1 each represent a unique subset. Total: 2^n masks.

2. Step 2: Loop bounds

   Start at 0 (mask=0 is the empty set - important to include). End at (1<

3. Step 3: Why not start at 1?

   Starting at 1 skips mask=0 which represents the empty subset.

4. Final Answer:

   mask from 0 to (1< -> Option B

5. Quick Check:

   mask=0 = empty set. mask=(1<

Hint: Bitmask loop: 0 to (1<

Common Mistakes:

• Starting at 1 and missing the empty subset
• Using <= (1<
• Looping to n instead of 2^n

5. What is the time complexity of generating all subsets of an n-element array using bitmask?

hard

A. O(n²)

B. O(n!)

C. O(n × 2^n)

D. O(2^n)

Solution

1. Step 1: Outer loop

   2^n iterations (one per mask).

2. Step 2: Inner loop

   For each mask, we check n bits to determine which elements are included → O(n) per mask.

3. Step 3: Total

   2^n masks × O(n) per mask = O(n × 2^n).

4. Final Answer:

   O(n × 2^n) -> Option C

5. Quick Check:

   2^n subsets × n work each = O(n × 2^n). [OK]

Hint: 2^n subsets × n bits to check each = O(n × 2^n). Same as backtracking approach. [OK]

Common Mistakes:

• Saying O(2^n) and forgetting the n factor for the inner bit-check loop
• Confusing with O(n!) which is for permutations
• Saying O(n²) which is far too fast