Subsets Generation Using Bitmask in DSA C - Build from Scratch

Subsets Generation Using Bitmask

📖 Scenario: Imagine you have a small collection of unique items, like three different colored balls: red, green, and blue. You want to find all possible groups (subsets) you can make from these balls, including the empty group and the group with all balls.

🎯 Goal: Build a program that uses bitmasking to generate and print all subsets of a given set of three items.

📋 What You'll Learn

Create an array called items with the exact strings: "red", "green", "blue"

Create an integer variable called n and set it to the number of items in the array

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

Inside the loop, use another for loop with variable i to check each bit of mask

Print each subset on a new line in the format: { item1 item2 } or { } for empty subset

💡 Why This Matters

🌍 Real World

Generating all possible combinations of options, like menu choices or feature sets, helps in planning and testing.

💼 Career

Understanding bitmasking and subsets is useful in coding interviews and solving problems in software development.

1

Create the items array

Create a string array called items with these exact values: "red", "green", "blue"

DSA C

# Create the items array with "red", "green", "blue"
// Your code here

Hint

Use char *items[] = {"red", "green", "blue"}; to create the array.

2

Create the variable for number of items

Create an integer variable called n and set it to the number of elements in items (which is 3)

DSA C

#include 

char *items[] = {"red", "green", "blue"};

// Create integer n and set it to 3
// Your code here

Hint

Use int n = 3; because there are 3 items.

3

Generate 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. Check if the i-th bit of mask is set using (mask & (1 << i)) != 0. If set, include items[i] in the current subset.

DSA C

#include 

char *items[] = {"red", "green", "blue"};

int n = 3;

// Use for loops with mask and i to generate subsets
// Your code here

Hint

Use nested loops and bitwise AND to check bits in mask.

4

Print all subsets

Add a printf statement inside the outer loop to print each subset in the format: { item1 item2 } or { } for empty subset. Use spaces after each item and print a newline after each subset.

DSA C

#include 

char *items[] = {"red", "green", "blue"};

int n = 3;

int main() {
    // Print all subsets here
    // Your code here
}

Hint

Make sure to print the opening and closing braces and a space after each item.

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