Subsets Generation Using Bitmask in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to generate all subsets of an array using bitmask.

DSA C#

for (int mask = 0; mask < (1 << [1]); mask++) {
    List<int> subset = new List<int>();
    for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) != 0) {
            subset.Add(arr[i]);
        }
    }
    // process subset
}

Drag options to blanks, or click blank then click option'

An

Barr.Length

Cmask

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Using arr.Length directly without storing in n.

Using mask or i in the bit shift instead of n.

The outer loop runs from 0 to 2^n - 1, where n is the number of elements. So we use n to shift 1 by n bits.

2fill in blank

medium

Complete the condition to check if the i-th element is included in the current subset.

DSA C#

if ((mask & (1 << [1])) != 0) {
    subset.Add(arr[i]);
}

Drag options to blanks, or click blank then click option'

Amask

Bi

Cn

Darr[i]

Attempts:

3 left

💡 Hint

Common Mistakes

Using mask or n instead of i in the bit shift.

Using arr[i] inside the bit shift.

We check the i-th bit of mask to see if the i-th element is included.

3fill in blank

hard

Fix the error in the code to correctly generate subsets using bitmask.

DSA C#

int n = arr.Length;
for (int mask = 0; mask [1] (1 << n); mask++) {
    List<int> subset = new List<int>();
    for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) != 0) {
            subset.Add(arr[i]);
        }
    }
    // process subset
}

Drag options to blanks, or click blank then click option'

A<

B>

C<=

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<=' causes one extra iteration leading to invalid subsets.

Using '>' or '>=' causes no iterations.

The loop should run while mask is less than 2^n, not less than or equal to, to avoid out of range.

4fill in blank

hard

Fill both blanks to create a dictionary mapping each subset's bitmask to its sum.

DSA C#

Dictionary<int, int> subsetSums = new Dictionary<int, int>();
for (int mask = 0; mask < (1 << n); mask++) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (mask [1] (1 << i) != 0) {
            sum [2] arr[i];
        }
    }
    subsetSums[mask] = sum;
}

Drag options to blanks, or click blank then click option'

A&

B+=

C|

D-=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '|' instead of '&' in the condition.

Using '-=' instead of '+=' for sum.

Use '&' to check if the i-th bit is set, and '+=' to add the element to sum.

5fill in blank

hard

Fill all three blanks to generate all subsets and print them.

DSA C#

int n = arr.Length;
for (int [1] = 0; [2] < (1 << n); [3]++) {
    List<int> subset = new List<int>();
    for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) != 0) {
            subset.Add(arr[i]);
        }
    }
    Console.WriteLine(string.Join(", ", subset));
}

Drag options to blanks, or click blank then click option'

Amask

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variable names causing errors.

Using i instead of mask for outer loop.

The outer loop variable is mask, used in initialization, condition, and increment.

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