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.

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