Subsets Generation Using Bitmask in DSA C++

Mental Model

Each subset can be represented by a series of on/off switches, where each switch decides if an element is included or not.

Analogy: Imagine you have a row of light switches, each controlling a lamp. Turning a switch on means including that lamp in the room's lighting; off means excluding it. Every combination of on/off switches creates a unique lighting setup, just like every combination of elements creates a unique subset.

Set: [a, b, c]
Bitmask positions: 2 1 0
Example bitmask: 101
Meaning: include a (bit 2), exclude b (bit 1), include c (bit 0)

Dry Run Walkthrough

Input: set: [1, 2, 3]

Goal: Generate all subsets of the set [1, 2, 3] using bitmask representation

Step 1: Start with bitmask 000 (0 in decimal), no elements included

bitmask=000 -> subset: []

Why: This represents the empty subset with no elements selected

Step 2: Bitmask 001 (1 in decimal), include element at position 0

bitmask=001 -> subset: [1]

Why: Only the first element is included because bit 0 is on

Step 3: Bitmask 010 (2 in decimal), include element at position 1

bitmask=010 -> subset: [2]

Why: Only the middle element is included because bit 1 is on

Step 4: Bitmask 011 (3 in decimal), include elements at positions 1 and 0

bitmask=011 -> subset: [1, 2]

Why: Bits 1 and 0 are on, so include elements 1 and 2

Step 5: Bitmask 100 (4 in decimal), include element at position 2

bitmask=100 -> subset: [3]

Why: Only the last element is included because bit 2 is on

Step 6: Bitmask 101 (5 in decimal), include elements at positions 2 and 0

bitmask=101 -> subset: [1, 3]

Why: Bits 2 and 0 are on, so include elements 1 and 3

Step 7: Bitmask 110 (6 in decimal), include elements at positions 2 and 1

bitmask=110 -> subset: [2, 3]

Why: Bits 2 and 1 are on, so include elements 2 and 3

Step 8: Bitmask 111 (7 in decimal), include all elements

bitmask=111 -> subset: [1, 2, 3]

Why: All bits are on, so include all elements

Result:

All subsets generated: [] [1] [2] [1, 2] [3] [1, 3] [2, 3] [1, 2, 3]

Annotated Code

DSA C++

#include <iostream>
#include <vector>

using namespace std;

// Function to generate all subsets using bitmask
vector<vector<int>> generateSubsets(const vector<int>& set) {
    vector<vector<int>> allSubsets;
    int n = set.size();
    int total = 1 << n; // 2^n subsets

    for (int bitmask = 0; bitmask < total; ++bitmask) {
        vector<int> subset;
        for (int j = 0; j < n; ++j) {
            if (bitmask & (1 << j)) {
                subset.push_back(set[j]);
            }
        }
        allSubsets.push_back(subset);
    }
    return allSubsets;
}

int main() {
    vector<int> set = {1, 2, 3};
    vector<vector<int>> subsets = generateSubsets(set);

    for (const auto& subset : subsets) {
        cout << "[";
        for (size_t i = 0; i < subset.size(); ++i) {
            cout << subset[i];
            if (i != subset.size() - 1) cout << ", ";
        }
        cout << "]\n";
    }
    return 0;
}

int total = 1 << n; // 2^n subsets

Calculate total number of subsets as 2 to the power n

for (int bitmask = 0; bitmask < total; ++bitmask) {

Iterate over all possible bitmasks representing subsets

if (bitmask & (1 << j)) {

Check if j-th bit is set in bitmask to include element j

subset.push_back(set[j]);

Add element j to current subset if bit is set

allSubsets.push_back(subset);

Add the generated subset to the list of all subsets

Output

[]

[1]

[2]

[1, 2]

[3]

[1, 3]

[2, 3]

[1, 2, 3]

Complexity Analysis

Time: O(n * 2^n) because we generate 2^n subsets and each subset can have up to n elements

Space: O(n * 2^n) because we store all subsets and each subset can have up to n elements

vs Alternative: Compared to recursive backtracking, bitmask uses iterative approach and is often simpler and faster for small sets

Edge Cases

empty set

Only one subset: the empty subset []

DSA C++

int total = 1 << n; // 2^n subsets

set with one element

Two subsets: [] and [element]

DSA C++

for (int bitmask = 0; bitmask < total; ++bitmask) {

When to Use This Pattern

When you need to generate all subsets of a set and want a simple, direct way to represent inclusion/exclusion, use bitmasking because it maps each subset to a binary number.

Common Mistakes

Mistake: Using 1 << j without parentheses causing wrong bit shift
Fix: Always use parentheses: (1 << j) to ensure correct bit shifting

Mistake: Iterating bitmask from 1 instead of 0, missing the empty subset
Fix: Start bitmask from 0 to include the empty subset

Summary

Generates all subsets of a set by treating each subset as a binary number where each bit decides inclusion.

Use when you want to list all possible combinations of elements quickly and clearly.

The key insight is that each subset corresponds to a unique bit pattern representing which elements are included.

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