Subsets Generation Using Bitmask in DSA C# - Build from Scratch

Subsets Generation Using Bitmask

📖 Scenario: Imagine you have a small collection of unique items, like three different colored balls: red, green, and blue. You want to find all the different groups (subsets) you can make from these balls, including the empty group and the group with all balls.

🎯 Goal: You will write a program that uses a bitmask technique to generate all possible subsets of a given list of items. This helps you understand how computers can represent and explore all combinations efficiently.

📋 What You'll Learn

Create a list of strings called items with exactly these values: "red", "green", "blue"

Create an integer variable called n that stores the number of items in the list

Use a for loop with variable mask from 0 to (1 << n) - 1 to generate all subsets

Inside the loop, use another for loop with variable i from 0 to n - 1 to check if the i-th bit in mask is set

Print each subset as a list of items separated by commas inside square brackets, e.g., [red, blue]

💡 Why This Matters

🌍 Real World

Generating subsets is useful in situations like choosing combinations of features, testing all possible options, or solving puzzles that require exploring all groups.

💼 Career

Understanding bitmasking and subsets helps in coding interviews, optimization problems, and tasks involving combinations and permissions.

1

Create the list of items

Create a list of strings called items with exactly these values: "red", "green", "blue"

DSA C#

# Create the list of items
// Your code here

Hint

Use List<string> and initialize it with the three colors inside curly braces.

2

Create the variable for number of items

Create an integer variable called n that stores the number of items in the list items

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List items = new List { "red", "green", "blue" };
        // Create variable n to store number of items
        // Your code here
    }
}

Hint

Use items.Count to get the number of items and assign it to n.

3

Generate all subsets using bitmask

Use a for loop with variable mask from 0 to (1 << n) - 1 to generate all subsets. Inside this loop, use another for loop with variable i from 0 to n - 1 to check if the i-th bit in mask is set. If it is, add items[i] to a temporary list called subset.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List items = new List { "red", "green", "blue" };
        int n = items.Count;

        // Generate all subsets using bitmask
        // Your code here
    }
}

Hint

Use bitwise AND & to check if the i-th bit of mask is set. If yes, add items[i] to subset.

4

Print each subset

Inside the for loop over mask, after building the subset list, print the subset as a list of items separated by commas inside square brackets. For example, print [red, blue] for a subset containing "red" and "blue". Print the empty subset as [].

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List items = new List { "red", "green", "blue" };
        int n = items.Count;

        for (int mask = 0; mask  subset = new List();
            for (int i = 0; i < n; i++)
            {
                if ((mask & (1 << i)) != 0)
                {
                    subset.Add(items[i]);
                }
            }
            // Print the subset here
            // Your code here
        }
    }
}

Hint

Use string.Join(", ", subset) to join items with commas, and print with square brackets around.

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