Generate All Subsets Powerset in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to start the recursive function call for generating all subsets.

DSA C

void generateSubsets(int arr[], int n) {
    int subset[[1]];
    generateSubsetsHelper(arr, n, 0, subset, 0);
}

Drag options to blanks, or click blank then click option'

A0

Bn+1

C1

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 or 1 as size causes no space for elements.

Using n+1 wastes extra space unnecessarily.

The subset array should have the same size as the input array to hold any subset.

2fill in blank

medium

Complete the base case condition to print the current subset when all elements are processed.

DSA C

void generateSubsetsHelper(int arr[], int n, int index, int subset[], int subsetSize) {
    if (index [1] n) {
        for (int i = 0; i < subsetSize; i++) {
            printf("%d ", subset[i]);
        }
        printf("\n");
        return;
    }
    // Recursive calls...
}

Drag options to blanks, or click blank then click option'

A<=

B>

C==

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using < or <= causes premature printing.

Using > never triggers base case.

When index equals n, all elements have been considered, so print the subset.

3fill in blank

hard

Fix the error in the recursive call that includes the current element in the subset.

DSA C

subset[subsetSize] = arr[index];
generateSubsetsHelper(arr, n, [1], subset, subsetSize + 1);

Drag options to blanks, or click blank then click option'

Aindex

Bindex + 1

CsubsetSize + 1

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Not incrementing index causes infinite recursion.

Using subsetSize instead of index is incorrect.

We move to the next index after including the current element.

4fill in blank

hard

Fill both blanks to correctly make the recursive call that excludes the current element.

DSA C

generateSubsetsHelper(arr, n, [1], subset, [2]);

Drag options to blanks, or click blank then click option'

Aindex + 1

Bindex

CsubsetSize

DsubsetSize + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Not incrementing index causes infinite recursion.

Increasing subsetSize when excluding element is wrong.

We skip the current element by moving index forward but keep subsetSize unchanged.

5fill in blank

hard

Fill all three blanks to complete the recursive function that generates all subsets.

DSA C

void generateSubsetsHelper(int arr[], int n, int index, int subset[], int subsetSize) {
    if (index [1] n) {
        for (int i = 0; i < subsetSize; i++) {
            printf("%d ", subset[i]);
        }
        printf("\n");
        return;
    }
    subset[subsetSize] = arr[index];
    generateSubsetsHelper(arr, n, [2], subset, subsetSize + 1);
    generateSubsetsHelper(arr, n, [3], subset, subsetSize);
}

Drag options to blanks, or click blank then click option'

A==

Bindex + 1

Cindex

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong base case condition.

Not incrementing index in recursive calls.

Base case when index == n; recursive calls increment index to include or exclude element.

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