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.