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.