Subsets Generation Using Bitmask in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of subsets generated by bitmask

What is the output of the following C code that generates all subsets of the array [1, 2, 3] using bitmask?

DSA C

#include <stdio.h>

int main() {
    int arr[] = {1, 2, 3};
    int n = 3;
    for (int mask = 0; mask < (1 << n); mask++) {
        printf("{");
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                printf("%d", arr[i]);
                if (i != n - 1) {
                    int j = i + 1;
                    while (j < n && !(mask & (1 << j))) j++;
                    if (j < n) printf(", ");
                }
            }
        }
        printf("}\n");
    }
    return 0;
}

A

{}
{3}
{2}
{1}
{3, 2}
{3, 1}
{2, 1}
{3, 2, 1}

B

{}
{1}
{2}
{3}
{1, 2}
{1, 3}
{2, 3}
{1, 2, 3}

C

{}
{1}
{3}
{2}
{1, 3}
{1, 2}
{3, 2}
{1, 3, 2}

D

{}
{1}
{2}
{1, 2}
{3}
{1, 3}
{2, 3}
{1, 2, 3}

💡 Hint

Remember that bitmask from 0 to 2^n - 1 represents subsets in increasing order.

The code iterates mask from 0 to 7 (2^3 - 1). For each mask, it prints elements where the bit is set. The order of subsets is by increasing mask value, so subsets appear in order: empty, {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, {1,2,3}.

🧠 Conceptual

intermediate

Number of subsets generated by bitmask for n elements

If you use bitmasking to generate all subsets of a set with n elements, how many subsets will be generated?

A n!

B 2^n

C n^2

D n

💡 Hint

Each element can be either included or excluded independently.

Each element has two choices: included or excluded. So total subsets = 2 * 2 * ... * 2 (n times) = 2^n.

🔧 Debug

advanced

Identify the error in subset generation code

What error does the following C code produce when generating subsets using bitmask for array [1, 2, 3]? #include int main() { int arr[] = {1, 2, 3}; int n = 3; 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"); } return 0; }

A Runs but prints one extra empty subset at the end

B Runs correctly and prints all subsets

C Runs but causes an infinite loop

D Causes a runtime error due to out-of-bounds access

💡 Hint

Check the loop condition for mask variable.

The loop runs from mask = 0 to mask = 8 (inclusive). Since 1 << 3 = 8, mask=8 is out of range for subsets of 3 elements (max mask is 7). So it prints an extra empty subset for mask=8.

🚀 Application

advanced

Find subsets with sum equal to target using bitmask

Given array [2, 4, 6, 10] and target sum 16, which subsets are printed by the following code snippet? #include int main() { int arr[] = {2, 4, 6, 10}; int n = 4; int target = 16; for (int mask = 0; mask < (1 << n); mask++) { int sum = 0; for (int i = 0; i < n; i++) { if (mask & (1 << i)) { sum += arr[i]; } } if (sum == target) { printf("{"); int first = 1; for (int i = 0; i < n; i++) { if (mask & (1 << i)) { if (!first) printf(", "); printf("%d", arr[i]); first = 0; } } printf("}\n"); } } return 0; }

A

{2, 4, 10}
{6, 10}

B

{2, 6, 10}
{4, 6, 10}

C {4, 6, 10}

D {2, 4, 6, 10}

💡 Hint

Calculate sums of subsets and check which equal 16.

Subsets with sum 16 are {2, 4, 10} (2+4+10=16) and {6, 10} (6+10=16).

❓ Predict Output

expert

Output of bitmask subset generation with duplicate elements

What is the output of the following C code that generates all subsets of the array [1, 2, 2] using bitmask?

DSA C

#include <stdio.h>

int main() {
    int arr[] = {1, 2, 2};
    int n = 3;
    for (int mask = 0; mask < (1 << n); mask++) {
        printf("{");
        int first = 1;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                if (!first) printf(", ");
                printf("%d", arr[i]);
                first = 0;
            }
        }
        printf("}\n");
    }
    return 0;
}

A

{}
{1}
{2}
{2}
{2, 2}
{1, 2}
{1, 2}
{1, 2, 2}

B

{}
{1}
{2}
{1, 2}
{2}
{2, 2}
{1, 2}
{1, 2, 2}

C

{}
{1}
{2}
{1, 2}
{2}
{1, 2}
{2, 2}
{1, 2, 2}

D

{}
{1}
{2}
{2}
{1, 2}
{1, 2}
{2, 2}
{1, 2, 2}

💡 Hint

Bitmask order is from 0 to 7, each bit representing element inclusion.

The subsets correspond to masks 0 to 7: 0: {} 1: {1} 2: {2} (second element) 3: {1, 2} (first and second bits set: arr[0] and arr[1]) 4: {2} (third element) 5: {1, 2} (arr[0] and arr[2]) 6: {2, 2} (arr[1] and arr[2]) 7: {1, 2, 2} (all elements) Option C matches this order.

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