Generate All Subsets Powerset in DSA C - Execution Trace

Concept Flow - Generate All Subsets Powerset

Start with empty subset

↓

Pick next element

↓

Two choices: Include or Exclude

↓

Include element

↓

Add subset to result if at end

↓

Backtrack to previous step

↩Back to Pick next element

Start with an empty subset, then for each element, choose to include or exclude it, recursively building all subsets.

Execution Sample

DSA C

void generateSubsets(int arr[], int n, int index, int subset[], int subsetSize) {
    if (index == n) {
        printSubset(subset, subsetSize);
        return;
    }
    generateSubsets(arr, n, index + 1, subset, subsetSize);
    subset[subsetSize] = arr[index];
    generateSubsets(arr, n, index + 1, subset, subsetSize + 1);
}

This code recursively generates all subsets by excluding or including each element.

Execution Table

Step	Operation	Current Index	Subset Being Built	Action Taken	Visual State of Subsets
1	Start	0	[]	Begin recursion	[]
2	Exclude element 1	1	[]	Exclude arr[0]=1	[]
3	Exclude element 2	2	[]	Exclude arr[1]=2	[]
4	Exclude element 3	3	[]	Exclude arr[2]=3	[]
5	Add subset	3	[]	Reached end, add []	[[]]
6	Include element 3	3	[3]	Include arr[2]=3	[[], [3]]
7	Backtrack to index 2	2	[]	Backtrack	[[], [3]]
8	Include element 2	2	[2]	Include arr[1]=2	[[], [3]]
9	Exclude element 3	3	[2]	Exclude arr[2]=3	[[], [3], [2]]
10	Add subset	3	[2]	Reached end, add [2]	[[], [3], [2]]
11	Include element 3	3	[2,3]	Include arr[2]=3	[[], [3], [2], [2,3]]
12	Backtrack to index 1	1	[]	Backtrack	[[], [3], [2], [2,3]]
13	Include element 1	1	[1]	Include arr[0]=1	[[], [3], [2], [2,3]]
14	Exclude element 2	2	[1]	Exclude arr[1]=2	[[], [3], [2], [2,3]]
15	Exclude element 3	3	[1]	Exclude arr[2]=3	[[], [3], [2], [2,3], [1]]
16	Add subset	3	[1]	Reached end, add [1]	[[], [3], [2], [2,3], [1]]
17	Include element 3	3	[1,3]	Include arr[2]=3	[[], [3], [2], [2,3], [1], [1,3]]
18	Backtrack to index 2	2	[1]	Backtrack	[[], [3], [2], [2,3], [1], [1,3]]
19	Include element 2	2	[1,2]	Include arr[1]=2	[[], [3], [2], [2,3], [1], [1,3]]
20	Exclude element 3	3	[1,2]	Exclude arr[2]=3	[[], [3], [2], [2,3], [1], [1,3], [1,2]]
21	Add subset	3	[1,2]	Reached end, add [1,2]	[[], [3], [2], [2,3], [1], [1,3], [1,2]]
22	Include element 3	3	[1,2,3]	Include arr[2]=3	[[], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]]
23	End	3	[]	All subsets generated	[[], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]]

💡 Index reaches array length (3), recursion ends and all subsets are generated.

Variable Tracker

Variable	Start	After Step 5	After Step 11	After Step 17	After Step 22	Final
index	0	3	3	3	3	3
subset	[]	[]	[2,3]	[1,3]	[1,2,3]	[]
subsetSize	0	0	2	2	3	0
subsets_collected	[]	[[]]	[[], [3], [2], [2,3]]	[[], [3], [2], [2,3], [1], [1,3]]	[[], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]]	[[], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]]

Key Moments - 3 Insights

Why do we call the recursive function twice at each step?

Because at each index, we have two choices: exclude or include the current element. The execution_table rows 2 and 13 show these two calls for index 0.

How do we know when to add the current subset to the result?

When the index reaches the length of the array (step 5, 10, 16, 21), we add the current subset because we have considered all elements.

Why does the subset array change after including an element but not after excluding?

Excluding does not add the element, so subset stays the same (see steps 2, 3, 4). Including adds the element at subsetSize position (steps 6, 11).

Visual Quiz - 3 Questions

Look at the execution_table at step 11. What is the subset being built?

A []

B [3]

C [2,3]

D [1,3]

💡 Hint

Check the 'Subset Being Built' column at step 11 in the execution_table.

At which step does the recursion first add the empty subset to the result?

A Step 4

B Step 5

C Step 6

D Step 7

💡 Hint

Look for the first 'Add subset' action with an empty subset in the execution_table.

If we change the input array to have 2 elements instead of 3, how many subsets will be generated?

A 4

B 3

C 2

D 8

💡 Hint

Recall that the number of subsets is 2^n, where n is the number of elements.

Concept Snapshot

Generate All Subsets (Powerset):
- Use recursion with index to track position
- At each step, choose to include or exclude current element
- When index == n, add current subset to result
- Total subsets = 2^n
- Backtracking builds all combinations

Full Transcript

This concept shows how to generate all subsets of an array using recursion. We start with an empty subset and at each element, we decide to include or exclude it. This creates two recursive calls per element. When we reach the end of the array, we add the current subset to the result. The execution table tracks each step, showing the current index, subset being built, and the subsets collected so far. The variable tracker shows how index and subset change over time. Key moments clarify why two recursive calls happen and when subsets are added. The visual quiz tests understanding of subset states and counts. The snapshot summarizes the approach and key rules.

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