Generate All Subsets Powerset in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of powerset generation with recursion

What is the output of this C code that generates all subsets (powerset) of the array {1, 2}?

DSA C

#include <stdio.h>

void printSubset(int subset[], int size) {
    printf("{");
    for (int i = 0; i < size; i++) {
        printf("%d", subset[i]);
        if (i < size - 1) printf(", ");
    }
    printf("}\n");
}

void generatePowerset(int arr[], int n, int index, int subset[], int subsetSize) {
    if (index == n) {
        printSubset(subset, subsetSize);
        return;
    }
    // Exclude current element
    generatePowerset(arr, n, index + 1, subset, subsetSize);
    // Include current element
    subset[subsetSize] = arr[index];
    generatePowerset(arr, n, index + 1, subset, subsetSize + 1);
}

int main() {
    int arr[] = {1, 2};
    int subset[2];
    generatePowerset(arr, 2, 0, subset, 0);
    return 0;
}

A

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

B

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

C

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

D

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

💡 Hint

Trace the recursion tree: first exclude, then include each element.

The recursion first excludes all elements printing {}, then includes 2 (excluding 1) printing {2}, then includes 1 excluding 2 printing {1}, then includes both {1, 2}.

❓ Predict Output

intermediate

Output of iterative powerset generation

What is the output of this C code that generates all subsets (powerset) of the array {1, 2} using bit manipulation?

DSA C

#include <stdio.h>

void printSubset(int arr[], int n, int bitmask) {
    printf("{");
    int first = 1;
    for (int i = 0; i < n; i++) {
        if (bitmask & (1 << i)) {
            if (!first) printf(", ");
            printf("%d", arr[i]);
            first = 0;
        }
    }
    printf("}\n");
}

int main() {
    int arr[] = {1, 2};
    int n = 2;
    for (int bitmask = 0; bitmask < (1 << n); bitmask++) {
        printSubset(arr, n, bitmask);
    }
    return 0;
}

A

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

B

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

C

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

D

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

💡 Hint

Bitmask 0 means empty set, bitmask 1 means include first element, etc.

The loop goes from 0 to 3 (binary 00 to 11), printing subsets in increasing bitmask order.

🧠 Conceptual

advanced

Number of subsets in powerset

Given an array of size n, how many subsets does its powerset contain?

A n

B n^2

C 2^n

D n!

💡 Hint

Each element can be either included or excluded.

Each element has 2 choices: in or out, so total subsets = 2^n.

🔧 Debug

advanced

Identify the bug in powerset recursion

What error does this code produce when generating powerset of {1, 2}? void generate(int arr[], int n, int index, int subset[], int size) { if (index > n) { printSubset(subset, size); return; } generate(arr, n, index + 1, subset, size); subset[size] = arr[index]; generate(arr, n, index + 1, subset, size + 1); }

A Segmentation fault due to out-of-bounds access

B No output printed

C Infinite recursion

D Compilation error due to missing return type

💡 Hint

Check the base case condition for index.

The base case should be index == n, but here index > n allows index == n which causes arr[n] access out of bounds.

🚀 Application

expert

Count subsets with sum equal to target

Given an array {1, 2, 3} and target sum 3, how many subsets have sum exactly 3?

A 4

B 2

C 3

D 1

💡 Hint

List all subsets and check their sums.

Subsets with sum 3 are {3} and {1, 2}, total 2 subsets.