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

↓

For each bit position

↓

If bit is 1, include element

↓

Form subset

↓

Add subset to result

↓

Repeat until all numbers processed

↓

Return all subsets

This flow shows how each number from 0 to 2^n - 1 is used as a bitmask to pick elements from the input set to form all possible subsets.

Execution Sample

DSA C++

vector<int> nums = {1, 2, 3};
int n = nums.size();
for (int mask = 0; mask < (1 << n); ++mask) {
  vector<int> subset;
  for (int i = 0; i < n; ++i) {
    if (mask & (1 << i)) subset.push_back(nums[i]);
  }
  // subset ready
}

This code generates all subsets of {1, 2, 3} by using bitmask from 0 to 7, including elements where the bit is set.

Execution Table

Step	Mask (binary)	Operation	Subset Formed	Visual State
1	000	No bits set, empty subset	{}	{}
2	001	Bit 0 set, include nums[0]=1	{1}	{1}
3	010	Bit 1 set, include nums[1]=2	{2}	{2}
4	011	Bits 0 and 1 set, include nums[0]=1, nums[1]=2	{1, 2}	{1 -> 2}
5	100	Bit 2 set, include nums[2]=3	{3}	{3}
6	101	Bits 0 and 2 set, include nums[0]=1, nums[2]=3	{1, 3}	{1 -> 3}
7	110	Bits 1 and 2 set, include nums[1]=2, nums[2]=3	{2, 3}	{2 -> 3}
8	111	Bits 0,1,2 set, include nums[0]=1, nums[1]=2, nums[2]=3	{1, 2, 3}	{1 -> 2 -> 3}
9	-	All masks processed, subsets complete	All subsets generated	Complete

💡 Mask reaches 2^3=8, loop ends after processing mask 111 (7 in decimal)

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 (exit)
subset	{}	{}	{1}	{2}	{1, 2}	{3}	{1, 3}	{2, 3}	{1, 2, 3}	N/A
i (bit index)	0	0-2	0-2	0-2	0-2	0-2	0-2	0-2	0-2	N/A

Key Moments - 3 Insights

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

Because each bit in mask represents whether to include an element. For n elements, 2^n combinations exist, so mask covers all subsets. See execution_table rows 1 to 8.

How do bits in mask correspond to elements?

Each bit position i in mask corresponds to nums[i]. If bit is 1, nums[i] is included in subset. Refer to execution_table rows 2, 4, 6 for examples.

Why is the empty subset generated at mask 0?

Mask 0 has no bits set, so no elements are included, resulting in empty subset. See execution_table row 1.

Visual Quiz - 3 Questions

Look at the execution_table, what subset is formed at Step 6 (mask 101)?

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 all bits set for the input {1,2,3}?

A Step 4

B Step 8

C Step 5

D Step 2

💡 Hint

Look for mask '111' in the 'Mask (binary)' column in execution_table.

If the input set had 4 elements, how many total subsets would the mask loop run?

A 8

B 15

C 16

D 32

💡 Hint

Recall total subsets = 2^n; for n=4, 2^4 = 16.

Concept Snapshot

Subsets Generation Using Bitmask:
- Use numbers 0 to 2^n - 1 as bitmasks
- Each bit represents inclusion of element at that index
- For each mask, build subset by checking bits
- Generates all 2^n subsets including empty
- Efficient and simple for small n

Full Transcript

This concept shows how to generate all subsets of a set using bitmasking. We use numbers from 0 to 2^n - 1, where n is the number of elements. Each bit in the number tells us whether to include the element at that position. For example, mask 101 means include elements at positions 0 and 2. We loop through all masks, build subsets accordingly, and collect all subsets. The empty subset corresponds to mask 0 with no bits set. This method efficiently lists all subsets without recursion.

Practice

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

easy

A. Only the largest subset of the set

B. All possible subsets of the set

C. The sum of all elements in the set

D. The sorted version of the set

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 over all bitmasks from 0 to 2^n - 1, we get all possible subsets of the set.

3. Final Answer:

   All possible subsets of the set -> Option B

4. Quick Check:

   Bitmask = subsets generator [OK]

Hint: Bitmask bits map directly to subset elements included [OK]

Common Mistakes:

• Thinking bitmask generates only one subset
• Confusing subsets with permutations
• Assuming bitmask sorts elements

2. Which of the following is the correct C++ syntax to iterate over all bitmasks for a set of size n?

easy

A. for (int mask = 0; mask <= n; mask++)

B. for (int mask = 1; mask <= n; mask++)

C. for (int mask = 0; mask < (1 << n); mask++)

D. for (int mask = 0; mask < n; mask++)

Solution

1. Step 1: Understand bitmask range

   Bitmask ranges from 0 to 2^n - 1, which is (1 << n) - 1 in C++.

2. Step 2: Correct loop syntax

   The loop must run from 0 to less than (1 << n) to cover all subsets.

3. Final Answer:

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

4. Quick Check:

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

Hint: Use (1 << n) for 2^n subsets count [OK]

Common Mistakes:

• Using mask <= n instead of mask < (1 << n)
• Starting loop from 1 instead of 0
• Using mask < n which is too small

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

std::vector<int> nums = {1, 2};
for (int mask = 0; mask < (1 << 2); mask++) {
    std::cout << "Subset: ";
    for (int i = 0; i < 2; i++) {
        if (mask & (1 << i)) std::cout << nums[i] << " ";
    }
    std::cout << std::endl;
}

medium

A. Subset:
Subset: 1
Subset: 2
Subset: 1 2

B. Subset: 1 2
Subset: 1
Subset: 2
Subset:

C. Subset: 1
Subset: 2
Subset: 1 2
Subset:

D. Subset:
Subset: 2
Subset: 1
Subset: 1 2

Solution

1. Step 1: Identify bitmask values and subsets

   For n=2, masks go 0 to 3:
   0 (00) no elements,
   1 (01) includes nums[0]=1,
   2 (10) includes nums[1]=2,
   3 (11) includes nums[0]=1 and nums[1]=2.

2. Step 2: Match output lines to subsets

   Output lines print subsets in order:
   "Subset: " (empty),
   "Subset: 1 ",
   "Subset: 2 ",
   "Subset: 1 2 "

3. Final Answer:

   Subset: Subset: 1 Subset: 2 Subset: 1 2 -> Option A

4. Quick Check:

   Bitmask 0 to 3 prints subsets in order [OK]

Hint: Map bits to elements; 0 means exclude, 1 means include [OK]

Common Mistakes:

• Mixing order of subsets
• Printing elements in wrong bit order
• Skipping empty subset output

4. Identify the error in the following code snippet for generating subsets using bitmask:

std::vector<int> nums = {1, 2, 3};
for (int mask = 0; mask <= (1 << nums.size()); mask++) {
    for (int i = 0; i < nums.size(); i++) {
        if (mask & (1 << i)) std::cout << nums[i] << " ";
    }
    std::cout << std::endl;
}

medium

A. The vector nums should be declared as std::list instead.

B. The inner loop should run from i = 1 to nums.size().

C. The bitwise AND operator & should be replaced with &&.

D. The loop condition should be mask < (1 << nums.size()), not <=.

Solution

1. Step 1: Analyze loop range for bitmask

   The bitmask must go from 0 to 2^n - 1, so mask < (1 << n). Using <= causes one extra iteration beyond valid range.

2. Step 2: Check other parts

   Inner loop from 0 is correct, bitwise AND & is correct, vector type is fine.

3. Final Answer:

   The loop condition should be mask < (1 << nums.size()), not <=. -> Option D

4. Quick Check:

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

Hint: Use <, not <=, for bitmask loop upper bound [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Replacing bitwise & with logical &&
• Starting inner loop at 1 instead of 0

5. Given a set nums = {1, 2, 2}, which code modification correctly generates all unique subsets using bitmask technique in C++?

hard

A. Use a std::set<std::vector<int>> to store subsets and sort each subset before insertion.

B. Use bitmask from 1 to (1 << n) and print subsets directly without sorting.

C. Use a std::map<int, int> to count elements and generate subsets.

D. Skip duplicates by checking if current element equals previous without sorting.

Solution

1. Step 1: Understand duplicate issue in subsets

   With duplicates in input, bitmask generates duplicate subsets. Sorting subsets before storing helps identify duplicates.

2. Step 2: Use std::set to store unique subsets

   Storing sorted subsets in a set automatically removes duplicates, ensuring unique subsets only.

3. Final Answer:

   Use a std::set<std::vector<int>> to store subsets and sort each subset before insertion. -> Option A

4. Quick Check:

   Sort subsets + set = unique subsets [OK]

Hint: Sort subsets and use set to avoid duplicates [OK]

Common Mistakes:

• Not sorting subsets before inserting in set
• Using map instead of set for uniqueness
• Ignoring duplicates without sorting