Subsets Generation Using Bitmask in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

🧠 Conceptual

easy

Bitmask and Subset Correspondence

For an array of 3 elements [a, b, c], which bitmask (in binary) represents the subset {a, c}?

A 101

B 010

C 110

D 011

💡 Hint

Assign bit 0 to element a (rightmost), bit 1 to b, bit 2 to c. A set bit means the element is included.

With bit 0 → a, bit 1 → b, bit 2 → c: subset {a, c} includes a (bit 0 = 1) and c (bit 2 = 1) but not b (bit 1 = 0). Binary: 101. In decimal: 5. The bitmask approach uses each integer from 0 to 2^n - 1, with each bit position representing whether the corresponding element is included.

❓ Predict Output

intermediate

Bitmask Subset Count

What does this C# code print for nums = [1, 2, 3]?

DSA C#

int n = 3;
int total = 1 << n;
Console.WriteLine(total);

A 3

B 6

C 9

D 8

💡 Hint

1 << n shifts 1 left by n positions, equivalent to 2^n.

1 << 3 = 2^3 = 8. This is the total number of subsets for a 3-element array. Bitmasks 0 through 7 (binary 000 to 111) each represent one unique subset. The loop to generate all subsets iterates mask from 0 to (1 << n) - 1.

🔧 Debug

intermediate

Fix the Bit Check

This C# code is supposed to check if bit j is set in mask, but it always returns true. What is the bug?

DSA C#

bool IsBitSet(int mask, int j) {
    return (mask | (1 << j)) != 0;  // BUG
}

A Should use ^ instead of |

B Should use & instead of |

C Should use ~ instead of |

D Should compare to 1 instead of 0

💡 Hint

OR sets bits — it can never decrease a value to 0. What operation isolates a specific bit?

mask | (1 << j) always sets bit j, making the result always non-zero — so it always returns true regardless of the original mask. The correct check uses AND: (mask & (1 << j)) != 0. AND isolates bit j — if it was already set in mask, the result is non-zero (true); if it wasn't set, the result is 0 (false).

🚀 Application

intermediate

Complete the Bitmask Subset Generator

Which option correctly completes the inner loop to print elements for each subset?

DSA C#

int[] nums = {1, 2, 3};
int n = nums.Length;
for (int mask = 0; mask < (1 << n); mask++) {
    var subset = new List<int>();
    for (int j = 0; j < n; j++) {
        if (/* CONDITION */) {
            subset.Add(nums[j]);
        }
    }
    Console.WriteLine("[" + string.Join(",", subset) + "]");
}

A (mask & (1 << j)) != 0

B (mask | (1 << j)) != 0

C (mask ^ (1 << j)) != 0

D mask > j

💡 Hint

We want to check if bit j is set in mask — which bitwise operation isolates a specific bit?

(mask & (1 << j)) != 0 checks whether bit j is set in mask. If set, element j is part of this subset and is added to the list. This correctly maps each bit position to its corresponding element: bit 0 → nums[0], bit 1 → nums[1], bit 2 → nums[2].

🧠 Conceptual

hard

Bitmask vs Backtracking Trade-off

Compared to the backtracking approach for subset generation, what is the key advantage of the bitmask approach?

A Bitmask uses less memory because it never stores the subsets

B Bitmask runs in O(n) time while backtracking is O(2^n)

C Bitmask is iterative with no recursion overhead — simpler call stack and predictable iteration order using integer counting

D Bitmask can handle duplicate elements without extra logic

💡 Hint

Think about recursion depth, stack frames, and how the bitmask approach iterates through subsets.

The bitmask approach replaces recursion with a simple integer counter from 0 to 2^n - 1. No recursive function calls, no call stack growth, no risk of stack overflow for large n. The iteration order is deterministic (numeric order of masks). Both approaches generate exactly 2^n subsets in O(n × 2^n) total time — the time complexity is the same, but bitmask is simpler and more cache-friendly.

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