Subsets Generation Using Bitmask in DSA C++ - Build from Scratch

Subsets Generation Using Bitmask

📖 Scenario: Imagine you have a small collection of unique fruits and you want to see all possible combinations of these fruits you can pick. This is like making different fruit baskets with any number of fruits from your collection.

🎯 Goal: You will write a C++ program that generates all possible subsets (combinations) of a given list of fruits using a bitmask technique.

📋 What You'll Learn

Create a vector of strings called fruits with exactly these values: "apple", "banana", "cherry"

Create an integer variable called n that stores the size of the fruits vector

Use a for loop with variable mask from 0 to (1 << n) - 1 to generate all subsets

Inside the loop, use another for loop with variable i from 0 to n - 1 to check if the i-th bit in mask is set

Print each subset on a new line with fruits separated by spaces, or print Empty if the subset has no fruits

💡 Why This Matters

🌍 Real World

Generating all combinations of items is useful in shopping apps, menu planning, and testing different feature sets.

💼 Career

Understanding subsets and bitmasking is important for coding interviews and solving problems involving combinations efficiently.

1

Create the fruits list

Create a std::vector<std::string> called fruits with these exact values: "apple", "banana", "cherry"

DSA C++

#include 
#include 
#include 

int main() {
    // Create the fruits vector here

    return 0;
}

Hint

Use std::vector<std::string> and initialize it with the three fruit names inside curly braces.

2

Create the size variable

Create an integer variable called n and set it to the size of the fruits vector using fruits.size()

DSA C++

#include 
#include 
#include 

int main() {
    std::vector fruits = {"apple", "banana", "cherry"};
    // Create the integer n to store the size of fruits

    return 0;
}

Hint

Use int n = fruits.size(); to get the number of fruits.

3

Generate all subsets using bitmask

Use a for loop with variable mask from 0 to (1 << n) - 1. Inside it, use another for loop with variable i from 0 to n - 1 to check if the i-th bit in mask is set using (mask & (1 << i)). If set, print fruits[i] followed by a space.

DSA C++

#include 
#include 
#include 

int main() {
    std::vector fruits = {"apple", "banana", "cherry"};
    int n = fruits.size();

    // Use a for loop with mask from 0 to (1 << n) - 1
    // Inside, use a for loop with i from 0 to n - 1
    // Check if (mask & (1 << i)) is true
    // If yes, print fruits[i] followed by a space

    return 0;
}

Hint

Use nested loops: outer loop for mask, inner loop for i. Use bitwise AND to check bits.

4

Print subsets or Empty if none

Modify the inner loop to print Empty if no fruits are printed for a subset. Use a boolean variable empty set to true before the inner loop and set it to false if any fruit is printed. After the inner loop, if empty is still true, print Empty. Then print a newline.

DSA C++

#include 
#include 
#include 

int main() {
    std::vector fruits = {"apple", "banana", "cherry"};
    int n = fruits.size();

    for (int mask = 0; mask < (1 << n); ++mask) {
        // Create a boolean empty and set it to true
        // Use a for loop with i from 0 to n - 1
        // If (mask & (1 << i)) is true, print fruits[i] and set empty to false
        // After the loop, if empty is true, print "Empty"
        // Print a newline
    }

    return 0;
}

Hint

Use a boolean flag to track if any fruit was printed. If none, print Empty.

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