Subsets Generation Using Bitmask in DSA C - Execution Trace

Concept Flow - Subsets Generation Using Bitmask

Start with input set

↓

Calculate total subsets = 2^n

↓

For each number from 0 to 2^n - 1

↓

Use bits of number as mask

↓

If bit j is 1, include element j

↓

Form subset

↓

Add subset to result

↓

Repeat until all subsets generated

↓

Done: All subsets generated

We generate all subsets by counting from 0 to 2^n - 1 and using each number's bits to decide which elements to include.

Execution Sample

DSA C

int n = 3;
int arr[] = {1, 2, 3};
for (int mask = 0; mask < (1 << n); mask++) {
  // For each bit j in mask
  // If bit j is set, include arr[j]
}

This code generates all subsets of {1, 2, 3} by using bitmask from 0 to 7.

Execution Table

Step	Mask (binary)	Operation	Subset Formed	Visual State
1	000	Mask 0: No bits set	{}	[]
2	001	Bit 0 set: Include arr[0]=1	{1}	[1]
3	010	Bit 1 set: Include arr[1]=2	{2}	[2]
4	011	Bits 0,1 set: Include arr[0]=1, arr[1]=2	{1,2}	[1,2]
5	100	Bit 2 set: Include arr[2]=3	{3}	[3]
6	101	Bits 0,2 set: Include arr[0]=1, arr[2]=3	{1,3}	[1,3]
7	110	Bits 1,2 set: Include arr[1]=2, arr[2]=3	{2,3}	[2,3]
8	111	Bits 0,1,2 set: Include arr[0]=1, arr[1]=2, arr[2]=3	{1,2,3}	[1,2,3]
9	-	mask reaches 8, loop ends	-	-

💡 mask reaches 8, which is 2^3, so all subsets generated

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
mask	0	0	1	2	3	4	5	6	7	8
subset	{}	{}	{1}	{2}	{1,2}	{3}	{1,3}	{2,3}	{1,2,3}	-

Key Moments - 3 Insights

Why does mask start from 0 and go to 2^n - 1?

Because each number from 0 to 2^n - 1 represents a unique combination of elements using bits, as shown in execution_table rows 1 to 8.

How do bits in mask decide which elements to include?

Each bit position corresponds to an element index; if bit j is 1, arr[j] is included. See execution_table rows 2, 4, 6 for examples.

What does the empty subset correspond to in bitmask?

The empty subset corresponds to mask 0 (binary 000), where no bits are set, so no elements are included, as in execution_table row 1.

Visual Quiz - 3 Questions

Look at the execution_table, what subset is formed at step 6?

A {1,3}

B {2,3}

C {1,2}

D {3}

💡 Hint

Check the 'Subset Formed' column at step 6 in execution_table.

At which step does the mask have bits 1 and 2 set (binary 110)?

A Step 5

B Step 7

C Step 4

D Step 8

💡 Hint

Look at the 'Mask (binary)' column in execution_table for bits 110.

If n was 2 instead of 3, how many steps would the loop run?

A 4

B 2

C 8

D 3

💡 Hint

Total subsets = 2^n, so for n=2, check variable_tracker mask final value.

Concept Snapshot

Subsets Generation Using Bitmask:
- For set of size n, total subsets = 2^n
- Loop mask from 0 to 2^n - 1
- Each bit in mask represents inclusion of element
- If bit j is 1, include element j
- Generates all subsets efficiently

Full Transcript

This concept shows how to generate all subsets of a set using bitmask numbers. We start with the input set and calculate total subsets as 2 to the power of n. Then, for each number from 0 to 2^n - 1, we use its bits to decide which elements to include in the subset. If a bit at position j is set to 1, we include the element at index j. This way, each number represents a unique subset. The execution table shows each step with the mask in binary, the subset formed, and the visual state of the subset. The variable tracker shows how the mask and subset change after each step. Key moments clarify why the mask runs from 0 to 2^n - 1, how bits decide inclusion, and what the empty subset means. The visual quiz tests understanding of subsets formed at specific steps and the total number of subsets for different n values. This method efficiently generates all subsets without recursion or complex logic.

Practice

1. What does the bitmask technique help to generate when applied to a set of elements?

easy

A. All possible subsets of the set

B. Only the largest subset of the set

C. Only subsets with even number of elements

D. Only subsets with odd number of elements

Solution

1. Step 1: Understand bitmask representation

   Each bit in the bitmask represents whether an element is included (1) or excluded (0) in a subset.

2. Step 2: Generate subsets using bitmask

   By iterating from 0 to 2^n - 1, all combinations of included/excluded elements are covered, producing all subsets.

3. Final Answer:

   All possible subsets of the set -> Option A

4. Quick Check:

   Bitmask = All subsets [OK]

Hint: Bitmask from 0 to 2^n-1 covers all subsets [OK]

Common Mistakes:

• Thinking bitmask generates only largest subsets
• Confusing bitmask with subsets of fixed size
• Assuming bitmask excludes empty subset

2. Which of the following C code snippets correctly initializes the loop to generate all subsets of an array of size n using bitmask?

easy

A. for (int mask = 0; mask < 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: Understand bitmask range

   Bitmask must cover all numbers from 0 to 2^n - 1, which is (1 << n) in C.

2. Step 2: Check loop conditions

   Loop from 0 to less than (1 << n) correctly iterates all subsets.

3. Final Answer:

   for (int mask = 0; mask < (1 << n); mask++) -> Option B

4. Quick Check:

   Loop from 0 to 2^n-1 [OK]

Hint: Use (1 << n) for 2^n in bitmask loops [OK]

Common Mistakes:

• Using mask <= n instead of mask < 2^n
• Starting loop from 1 excludes empty subset
• Using mask < n only covers n subsets

3. What is the output of the following C code snippet?

int arr[] = {1, 2};
int n = 2;
for (int mask = 0; mask < (1 << n); mask++) {
    printf("{");
    for (int i = 0; i < n; i++) {
        if (mask & (1 << i)) {
            printf("%d", arr[i]);
        }
    }
    printf("}\n");
}

medium

A. {}
{1}
{2}
{1, 2}

B. {}
{1}
{2}
{1 2}

C. {}
{1}
{2}
{12}

D. {}
{1}
{2}
{1}{2}

Solution

1. Step 1: Understand bitmask iterations

   mask goes from 0 to 3 (binary 00 to 11), representing subsets: empty, {1}, {2}, {1,2}.

2. Step 2: Trace output formatting

   Elements printed without spaces or commas, so subsets print as {}, {1}, {2}, {12}.

3. Final Answer:

   {} {1} {2} {12} -> Option C

4. Quick Check:

   Bitmask subsets printed without separators [OK]

Hint: Check print format carefully for separators [OK]

Common Mistakes:

• Assuming spaces or commas between elements
• Confusing bitmask order of elements
• Missing empty subset output

4. Identify the error in the following C code that attempts to generate subsets using bitmask:

int arr[] = {1, 2, 3};
int n = 3;
for (int mask = 0; mask <= (1 << n); mask++) {
    for (int i = 0; i < n; i++) {
        if (mask & (1 << i)) {
            printf("%d ", arr[i]);
        }
    }
    printf("\n");
}

medium

A. Loop condition should be mask < (1 << n), not <=

B. Bitwise AND operator is incorrect

C. Loop should start from 0 to include empty subset

D. Array indexing is out of bounds

Solution

1. Step 1: Check loop range correctness

   Loop runs from 0 to (1 << n) inclusive, which is 0 to 8 for n=3, but max mask should be 7 (0 to 7).

2. Step 2: Identify off-by-one error

   Using mask <= (1 << n) causes mask=8, which is out of valid subset range, causing incorrect behavior.

3. Final Answer:

   Loop condition should be mask < (1 << n), not <= -> Option A

4. Quick Check:

   Loop must run from 0 to 2^n - 1 [OK]

Hint: Use mask < (1 << n), not <= [OK]

Common Mistakes:

• Starting loop from 1 excludes empty subset
• Using <= causes out-of-range mask
• Misunderstanding bitwise AND usage

5. Given an array arr = {1, 2, 3, 4}, how many subsets generated by bitmask will have exactly two elements?

medium

A. 12

B. 4

C. 8

D. 6

Solution

1. Step 1: Calculate total subsets of size 2

   Number of subsets with exactly 2 elements from 4 elements is combination 4 choose 2 = 6.

2. Step 2: Understand bitmask filtering

   Among all 2^4=16 subsets, exactly 6 have two bits set in their bitmask representing two elements included.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   Combination(4,2) = 6 [OK]

Hint: Count subsets with 2 bits set = C(n,2) [OK]

Common Mistakes:

• Counting total subsets instead of size 2
• Confusing subsets with permutations
• Miscounting bitmask bits set