Generate All Subsets Powerset in DSA C

Mental Model

We find every possible group of items by deciding for each item if it is in or out.

Analogy: Imagine you have a box of colored balls and you want to see all ways to pick some or none of them. For each ball, you choose to keep it or leave it out, making all combinations.

Set: {1, 2}
Subsets:
[]
[1]
[2]
[1, 2]

Dry Run Walkthrough

Input: list: [1, 2]

Goal: Find all subsets including empty set and full set

Step 1: Start with empty subset []

[]

Why: We begin with no items selected

Step 2: Decide for item 1: include it

[1]

Why: Add item 1 to current subsets

Step 3: Decide for item 1: exclude it

[]

Why: Keep subset without item 1

Step 4: For each existing subset, decide for item 2: include it

[2], [1, 2]

Why: Add item 2 to all existing subsets

Step 5: For each existing subset, decide for item 2: exclude it

[], [1]

Why: Keep subsets without item 2

Result:

[]
[1]
[2]
[1, 2]

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.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 generateSubsets(int *nums, int n, int index, int *subset, int subsetSize) {
    if (index == n) {
        printSubset(subset, subsetSize); // print current subset
        return;
    }

    // Exclude current element
    generateSubsets(nums, n, index + 1, subset, subsetSize);

    // Include current element
    subset[subsetSize] = nums[index];
    generateSubsets(nums, n, index + 1, subset, subsetSize + 1);
}

int main() {
    int nums[] = {1, 2};
    int n = sizeof(nums) / sizeof(nums[0]);
    int *subset = (int *)malloc(n * sizeof(int));

    generateSubsets(nums, n, 0, subset, 0);

    free(subset);
    return 0;
}

if (index == n) { printSubset(subset, subsetSize); return; }

stop recursion and print current subset when all items considered

generateSubsets(nums, n, index + 1, subset, subsetSize);

explore subsets excluding current item

subset[subsetSize] = nums[index]; generateSubsets(nums, n, index + 1, subset, subsetSize + 1);

explore subsets including current item

Output

[]

[1]

[2]

[1, 2]

Complexity Analysis

Time: O(2^n) because each element can be either included or excluded, doubling subsets

Space: O(n) for recursion stack and temporary subset storage

vs Alternative: This backtracking approach is efficient and clear compared to iterative bitmasking which also takes O(2^n) time but is less intuitive

Edge Cases

empty input list

prints only the empty subset []

DSA C

if (index == n) { printSubset(subset, subsetSize); return; }

single element list

prints empty subset and subset with that single element

DSA C

if (index == n) { printSubset(subset, subsetSize); return; }

When to Use This Pattern

When you need to find all combinations or groups of items, use backtracking to include or exclude each item step by step.

Common Mistakes

Mistake: Not printing the subset when all items are considered
Fix: Add base case to print subset when index reaches end

Mistake: Modifying subset without backtracking or proper size tracking
Fix: Use subsetSize parameter to track current subset length and avoid overwriting

Summary

Generates every possible subset of a given list of items.

Use when you want to explore all combinations of elements.

The key is to decide for each item whether to include it or not, recursively.

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