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. Each pattern of switches on/off shows a different lighting setup, just like each bit pattern shows a different subset.

Set: [1, 2, 3]
Bitmask positions: 2 1 0
Example bitmask: 101
Subset: includes elements at positions with bit 1 -> [1, 3]

Dry Run Walkthrough

Input: set: [1, 2, 3]

Goal: Generate all subsets of the set using bitmask from 0 to 2^3 - 1

Step 1: Start with bitmask 000 (decimal 0), no bits set

bitmask=000 -> subset: []

Why: This represents the empty subset with no elements included

Step 2: Bitmask 001 (decimal 1), last bit set

bitmask=001 -> subset: [1]

Why: Only the last element (position 0) is included

Step 3: Bitmask 010 (decimal 2), middle bit set

bitmask=010 -> subset: [2]

Why: Only the second element (position 1) is included

Step 4: Bitmask 011 (decimal 3), last two bits set

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

Why: Elements at positions 0 and 1 included

Step 5: Bitmask 100 (decimal 4), first bit set

bitmask=100 -> subset: [3]

Why: Only the first element (position 2) is included

Step 6: Bitmask 101 (decimal 5), first and last bits set

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

Why: Elements at positions 0 and 2 included

Step 7: Bitmask 110 (decimal 6), first and middle bits set

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

Why: Elements at positions 1 and 2 included

Step 8: Bitmask 111 (decimal 7), all bits set

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

Why: All elements included, full set

Result:

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

Annotated Code

DSA C

#include <stdio.h>

void generate_subsets(int *set, int n) {
    int total = 1 << n; // total subsets = 2^n
    for (int bitmask = 0; bitmask < total; bitmask++) {
        printf("[");
        int first = 1;
        for (int j = 0; j < n; j++) {
            if (bitmask & (1 << j)) {
                if (!first) {
                    printf(", ");
                }
                printf("%d", set[j]);
                first = 0;
            }
        }
        printf("]\n");
    }
}

int main() {
    int set[] = {1, 2, 3};
    int n = sizeof(set) / sizeof(set[0]);
    generate_subsets(set, n);
    return 0;
}

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

Calculate total number of subsets using bit shift

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

Iterate through all bitmasks representing subsets

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

Check if j-th bit is set to include element at position j

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 check n bits for each

Space: O(n) for storing and printing each subset temporarily

vs Alternative: Compared to recursive subset generation, bitmask is iterative and often simpler to implement with direct bit operations

Edge Cases

empty set (n=0)

Only one subset: the empty subset []

DSA C

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

set with one element

Generates two subsets: [] and [element]

DSA C

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

When to Use This Pattern

When asked to list all subsets or combinations of a small set, use bitmasking to represent inclusion/exclusion efficiently.

Common Mistakes

Mistake: Confusing bit positions with element indices, leading to wrong subsets
Fix: Use consistent indexing and check bits with (1 << j) where j matches element position

Mistake: Printing subsets without commas or brackets, making output unclear
Fix: Use flags to print commas only between elements and enclose subsets in brackets

Summary

Generates all subsets of a set by treating each subset as a bit pattern where bits indicate element inclusion.

Use when you need to list or count all subsets of a small set efficiently.

The key insight is that each subset corresponds to a unique binary number from 0 to 2^n - 1.