Generate All Subsets Powerset in DSA C - Build from Scratch

Generate All Subsets Powerset

📖 Scenario: You are working on a simple program that helps a user find all possible combinations of items they have. This is useful when deciding which items to take on a trip or which ingredients to use in a recipe.

🎯 Goal: Build a program that generates all subsets (the powerset) of a given set of numbers. Each subset is a combination of elements from the original set, including the empty set.

📋 What You'll Learn

Create an array called nums with the exact values 1, 2, 3

Create an integer variable called n that stores the size of nums

Write a recursive function called generateSubsets that generates all subsets of nums

Use a helper array called current to store the current subset being built

Print each subset on a new line in the format: { } for empty set or {1 2} for subsets

Call the recursive function starting from index 0

Print all subsets including the empty set

💡 Why This Matters

🌍 Real World

Generating all subsets helps in decision making, like choosing combinations of products, ingredients, or features.

💼 Career

Understanding recursion and subsets is important for coding interviews and solving problems in software development.

1

Create the initial array

Create an integer array called nums with the exact values 1, 2, 3 and an integer variable called n that stores the size of nums.

DSA C

# Create the array nums and variable n
// Your code here

Hint

Use int nums[] = {1, 2, 3}; to create the array and int n = 3; for the size.

2

Add helper array for current subset

Add an integer array called current with size n to store the current subset being built, and an integer variable called index to track the current size of the subset.

DSA C

#include 

int nums[] = {1, 2, 3};
int n = 3;

// Create current array and index variable
// Your code here

Hint

Use int current[3]; and int index = 0; to prepare for building subsets.

3

Write recursive function to generate subsets

Write a recursive function called generateSubsets that takes an integer start as input. It should print the current subset stored in current up to index. Then, use a for loop with variable i from start to n - 1 to add nums[i] to current, increase index, call generateSubsets(i + 1), and then decrease index to backtrack.

DSA C

#include 

int nums[] = {1, 2, 3};
int n = 3;

int current[3];
int index = 0;

// Write generateSubsets function here
// Your code here

Hint

Print the current subset first, then use a loop to add elements and call the function recursively.

4

Call the function and print all subsets

In the main function, call generateSubsets(0) to print all subsets of nums. Then return 0.

DSA C

#include 

int nums[] = {1, 2, 3};
int n = 3;

int current[3];
int index = 0;

void generateSubsets(int start) {
    printf("{");
    for (int i = 0; i < index; i++) {
        printf("%d", current[i]);
        if (i < index - 1) {
            printf(" ");
        }
    }
    printf("}\n");

    for (int i = start; i < n; i++) {
        current[index] = nums[i];
        index++;
        generateSubsets(i + 1);
        index--;
    }
}

// Write main function to call generateSubsets
// Your code here

Hint

Call generateSubsets(0); inside main and return 0.

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