Subsets Generation Using Bitmask in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind generating subsets using bitmask?

Each subset can be represented by a binary number where each bit indicates whether an element is included (1) or excluded (0) from the subset.

beginner

How many subsets does a set with n elements have?

A set with n elements has 2^n subsets, including the empty set and the set itself.

intermediate

In C#, how do you check if the j-th bit in an integer i is set (1)?

Use the expression: (i & (1 << j)) != 0. It returns true if the j-th bit is 1, false otherwise.

intermediate

Why is bitmasking an efficient way to generate subsets?

Because it uses simple bitwise operations to represent inclusion/exclusion, avoiding recursion and reducing complexity in code.

beginner

What is the output of subsets generation using bitmask for the set [1, 2]?

The subsets are: [] (empty), [1], [2], [1, 2].

How many subsets will be generated for a set of 3 elements using bitmask?

A 8

B 6

C 9

D 3

A set with 3 elements has 2^3 = 8 subsets.

What does the bitmask 0101 represent for a set [a, b, c, d]?

A Subset with elements b and d

B Subset with elements a and c

C Subset with elements a and d

D Subset with elements b and c

Bits from right to left represent elements [a, b, c, d]. 0101 means bits 0 and 2 are set, so elements a and c are included.

Which operator is used to check if a bit is set in bitmasking?

A & (bitwise AND)

B | (bitwise OR)

C ^ (bitwise XOR)

D ~ (bitwise NOT)

The bitwise AND operator (&) is used to check if a specific bit is set.

What is the time complexity of generating all subsets using bitmask for n elements?

A O(n)

B O(2^n)

C O(n^2)

D O(2^n * n)

There are 2^n subsets and each subset can take up to n steps to build, so total complexity is O(2^n * n).

In C#, what does (1 << j) do?

A Performs bitwise AND between 1 and j

B Shifts j to the left by 1 bit

C Shifts 1 to the left by j bits

D Performs bitwise OR between 1 and j

(1 << j) shifts the binary 1 left by j positions, creating a mask to check or set the j-th bit.

Explain how to generate all subsets of a set using bitmasking in C#.

Think of binary numbers as switches for elements.

Describe the advantages of using bitmasking for subset generation compared to recursion.

Consider performance and code simplicity.

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