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.

Practice

1. What does the term powerset mean in the context of subsets?

easy

A. The largest subset of a given set

B. All possible subsets of a given set including empty and full set

C. Only the subsets with odd number of elements

D. Only the subsets with even number of elements

Solution

1. Step 1: Understand the definition of powerset

   The powerset of a set is the collection of all possible subsets, including the empty set and the set itself.

2. Step 2: Compare options with definition

   All possible subsets of a given set including empty and full set correctly describes all subsets including empty and full set. Other options limit subsets incorrectly.

3. Final Answer:

   All possible subsets of a given set including empty and full set -> Option B

4. Quick Check:

   powerset = all subsets [OK]

Hint: Powerset means every subset possible, including empty [OK]

Common Mistakes:

• Thinking powerset excludes empty set
• Confusing powerset with only even-sized subsets
• Assuming powerset means largest subset only

2. Which of the following C code snippets correctly initializes an empty subset list for generating a powerset?

easy

A. int subsets[1][1] = {{0}};

B. int subsets[0][0] = {{}};

C. int subsets[1][0] = {{}};

D. int subsets[1][0];

Solution

1. Step 1: Understand empty subset initialization in C

   An empty subset list for powerset starts with one subset: the empty set, which has zero elements.

2. Step 2: Check array dimensions and initialization

   int subsets[1][0] = {{}}; correctly declares an array with 1 subset of size 0, initialized empty. Other options have invalid sizes or syntax.

3. Final Answer:

   int subsets[1][0] = {{}}; -> Option C

4. Quick Check:

   Empty subset list = subsets[1][0] [OK]

Hint: Empty subset list has one subset with zero elements [OK]

Common Mistakes:

• Using zero subsets instead of one
• Incorrect array size for empty subset
• Invalid initialization syntax in C

3. What is the output of the following C code that generates all subsets of arr = {1, 2}?

#include 
void printSubsets(int arr[], int n) {
    int total = 1 << n;
    for (int i = 0; i < total; i++) {
        printf("{");
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {
                printf("%d ", arr[j]);
            }
        }
        printf("} ");
    }
}
int main() {
    int arr[] = {1, 2};
    printSubsets(arr, 2);
    return 0;
}

medium

A. {} {1} {2} {1 2}

B. {} {2} {1} {2 1}

C. {} {1} {2} {12}

D. {} {1} {2} {2 1}

Solution

1. Step 1: Understand bitmask iteration for subsets

   For n=2, total subsets = 4 (0 to 3). Each bit in i represents inclusion of arr[j].

2. Step 2: Trace output for each i

   i=0: no bits set -> {}
   i=1: bit0 set -> {1 }
   i=2: bit1 set -> {2 }
   i=3: bits0 and 1 set -> {1 2 }

3. Final Answer:

   {} {1} {2} {1 2} -> Option A

4. Quick Check:

   Bitmask subsets = {} {1} {2} {1 2} [OK]

Hint: Use bitmask from 0 to 2^n-1 to list subsets [OK]

Common Mistakes:

• Mixing order of elements in subsets
• Printing subsets without spaces
• Confusing bit positions with element order

4. Identify the error in the following C code snippet that attempts to generate all subsets of arr = {1, 2, 3}:

void generateSubsets(int arr[], int n) {
    int total = 1 << n;
    for (int i = 0; i <= total; i++) {
        printf("{");
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {
                printf("%d ", arr[j]);
            }
        }
        printf("}\n");
    }
}

medium

A. Missing initialization of variable i

B. Bitwise AND operator is used incorrectly

C. Inner loop should run from 1 to n instead of 0 to n-1

D. Loop runs one extra time causing out-of-range subsets

Solution

1. Step 1: Analyze loop range for total subsets

   Total subsets for n elements is 2^n, so loop should run from 0 to total-1.

2. Step 2: Identify off-by-one error

   Loop runs from i=0 to i=total (inclusive), which is one extra iteration causing invalid subset index.

3. Final Answer:

   Loop runs one extra time causing out-of-range subsets -> Option D

4. Quick Check:

   Loop limit = total-1, not total [OK]

Hint: Loop subsets from 0 to 2^n - 1 only [OK]

Common Mistakes:

• Using <= total instead of < total in loop
• Incorrect bitwise operations
• Wrong inner loop range

5. Given an array arr = {1, 2, 2}, which of the following C code modifications correctly generates all unique subsets (powerset without duplicates)?

hard

A. Sort array first, then skip duplicates while generating subsets

B. Use a hash set to store subsets and avoid duplicates

C. Generate all subsets normally without any change

D. Only generate subsets of size 1 and 2

Solution

1. Step 1: Understand duplicate subsets problem

   Array with duplicates can produce repeated subsets if not handled.

2. Step 2: Use sorting and skip duplicates approach

   Sorting arr groups duplicates together. While generating subsets, skip adding duplicate elements at the same recursion level to avoid repeated subsets.

3. Final Answer:

   Sort array first, then skip duplicates while generating subsets -> Option A

4. Quick Check:

   Sort + skip duplicates = unique subsets [OK]

Hint: Sort array and skip duplicates during subset generation [OK]

Common Mistakes:

• Ignoring duplicates causing repeated subsets
• Using hash sets without proper subset hashing
• Limiting subset sizes incorrectly