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.