Subsets Generation Using Bitmask in DSA C#

Mental Model

We use numbers in binary form to represent whether each item is included or not in a subset. Each bit is like a switch for an element.

Analogy: Imagine you have a row of light switches, one for each item. Turning a switch ON means including that item in the subset, OFF means excluding it. Counting from 0 to all switches ON gives all possible subsets.

Set: [1, 2, 3]
Bitmask: 0 0 0 -> empty subset
Bitmask: 0 1 0 -> subset with 2
Bitmask: 1 1 0 -> subset with 1 and 2
Bitmask: 1 1 1 -> subset with 1, 2, and 3

Dry Run Walkthrough

Input: set: [1, 2, 3]

Goal: Generate all subsets of the set [1, 2, 3] using bitmasking

Step 1: Start with bitmask 0 (000 in binary), no elements included

bitmask=000 -> subset: []

Why: This represents the empty subset with no elements selected

Step 2: Bitmask 1 (001): include element at index 0

bitmask=001 -> subset: [1]

Why: The rightmost bit is ON, so include first element

Step 3: Bitmask 2 (010): include element at index 1

bitmask=010 -> subset: [2]

Why: Second bit from right is ON, include second element

Step 4: Bitmask 3 (011): include elements at index 0 and 1

bitmask=011 -> subset: [1, 2]

Why: Bits 0 and 1 are ON, include first two elements

Step 5: Bitmask 4 (100): include element at index 2

bitmask=100 -> subset: [3]

Why: Third bit from right is ON, include third element

Step 6: Bitmask 5 (101): include elements at index 0 and 2

bitmask=101 -> subset: [1, 3]

Why: Bits 0 and 2 are ON, include first and third elements

Step 7: Bitmask 6 (110): include elements at index 1 and 2

bitmask=110 -> subset: [2, 3]

Why: Bits 1 and 2 are ON, include second and third elements

Step 8: Bitmask 7 (111): include all elements

bitmask=111 -> subset: [1, 2, 3]

Why: All bits ON means include all elements

Result:

All subsets generated: []
[1]
[2]
[1, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class SubsetsBitmask
{
    public static List<List<int>> GenerateSubsets(int[] nums)
    {
        int n = nums.Length;
        int total = 1 << n; // 2^n total subsets
        List<List<int>> result = new List<List<int>>();

        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) // check if bit i is set
                {
                    subset.Add(nums[i]);
                }
            }
            result.Add(subset);
        }
        return result;
    }

    static void Main()
    {
        int[] input = {1, 2, 3};
        var subsets = GenerateSubsets(input);
        foreach (var subset in subsets)
        {
            Console.WriteLine("[" + string.Join(", ", subset) + "]");
        }
    }
}

int total = 1 << n; // 2^n total subsets

Calculate total number of subsets as 2 to the power of n

for (int mask = 0; mask < total; mask++)

Iterate through all bitmasks representing subsets

if ((mask & (1 << i)) != 0)

Check if the i-th bit in mask is ON to include nums[i]

subset.Add(nums[i]);

Add element to current subset if bit is set

result.Add(subset);

Add the formed subset to the result list

Output

[]

[1]

[2]

[1, 2]

[3]

[1, 3]

[2, 3]

[1, 2, 3]

Complexity Analysis

Time: O(n * 2^n) because we generate all 2^n subsets and for each subset we check n bits

Space: O(n * 2^n) because we store all subsets and each subset can have up to n elements

vs Alternative: Compared to recursive backtracking, bitmasking is often simpler and uses iterative loops, but both have similar time complexity

Edge Cases

empty input array

Returns one subset: the empty subset []

DSA C#

int total = 1 << n; // 2^n total subsets

single element array

Returns two subsets: [] and [element]

DSA C#

for (int mask = 0; mask < total; mask++)

When to Use This Pattern

When you need to generate all subsets of a set and want a simple, direct way to represent inclusion/exclusion, use bitmasking because each bit naturally maps to an element's presence.

Common Mistakes

Mistake: Not using bitwise AND to check if a bit is set, causing wrong subsets
Fix: Use (mask & (1 << i)) != 0 to correctly check if the i-th bit is ON

Mistake: Looping mask from 1 to 2^n instead of 0 to 2^n - 1, missing the empty subset
Fix: Start mask from 0 to include the empty subset

Summary

Generates all subsets of a set by treating each subset as a binary number where bits represent element inclusion.

Use when you want to list every possible combination of elements quickly and clearly.

The key insight is that each bit in a number can represent whether an element is in or out of a subset.

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