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.