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.