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.