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

↓

Repeat until all elements processed

↓

Done

We start with an empty subset and for each element, we decide to include or exclude it, building all possible subsets step by step.

Execution Sample

DSA C#

void GenerateSubsets(int[] nums, int index, List<int> current, List<List<int>> result) {
  if (index == nums.Length) {
    result.Add(new List<int>(current));
    return;
  }
  GenerateSubsets(nums, index + 1, current, result);
  current.Add(nums[index]);
  GenerateSubsets(nums, index + 1, current, result);
  current.RemoveAt(current.Count - 1);
}

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

Execution Table

Step	Operation	Index	Current Subset	Action	Resulting Subsets
1	Start recursion	0	[]	At index 0, decide exclude/include	[]
2	Exclude 1	1	[]	Exclude element 1	[]
3	Exclude 2	2	[]	Exclude element 2	[]
4	Exclude 3	3	[]	Reached end, add []	[[]]
5	Include 3	3	[3]	Reached end, add [3]	[[], [3]]
6	Backtrack to index 2	2	[]	Include element 2	[]
7	Exclude 3	3	[2]	Reached end, add [2]	[[], [3], [2]]
8	Include 3	3	[2,3]	Reached end, add [2,3]	[[], [3], [2], [2,3]]
9	Backtrack to index 1	1	[]	Include element 1	[]
10	Exclude 2	2	[1]	Exclude element 2	[1]
11	Exclude 3	3	[1]	Reached end, add [1]	[[], [3], [2], [2,3], [1]]
12	Include 3	3	[1,3]	Reached end, add [1,3]	[[], [3], [2], [2,3], [1], [1,3]]
13	Backtrack to index 2	2	[1]	Include element 2	[1]
14	Exclude 3	3	[1,2]	Reached end, add [1,2]	[[], [3], [2], [2,3], [1], [1,3], [1,2]]
15	Include 3	3	[1,2,3]	Reached end, add [1,2,3]	[[], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]]
16	Backtrack complete	-	[]	All subsets generated	[[], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]]

💡 All elements processed, recursion ends with all subsets collected.

Variable Tracker

Variable	Start	After Step 4	After Step 8	After Step 12	After Step 15	Final
index	0	3	3	3	3	End
current subset	[]	[]	[2,3]	[1,3]	[1,2,3]	[]
resulting subsets	[]	[[]]	[[], [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 add the current subset to the result only when index == nums.Length?

Because at index == nums.Length, we have made include/exclude decisions for all elements, so the current subset is complete (see steps 4,5,7,8,11,12,14,15 in execution_table).

Why do we remove the last element after the second recursive call?

To backtrack and restore the current subset to its previous state before exploring other branches (see step 16 where current subset changes back to []).

How does the recursion explore all subsets?

At each index, it branches into two calls: one excluding and one including the current element, ensuring all combinations are covered (see steps 2-3 and 6-7).

Visual Quiz - 3 Questions

Look at the execution_table at step 8, what subsets have been added to the result?

A [[], [3], [2]]

B [[], [3], [1], [2,3]]

C [[], [3], [2], [2,3]]

D [[3], [2], [2,3]]

💡 Hint

Check the 'Resulting Subsets' column at step 8 in execution_table.

At which step does the recursion first include element 1 in the current subset?

A Step 12

B Step 9

C Step 5

D Step 2

💡 Hint

Look for when 'Include element 1' appears in the 'Action' column in execution_table.

If we remove the line that removes the last element after the second recursive call, what happens to the current subset?

A It grows indefinitely and includes all elements in every subset

B It remains empty throughout

C It only contains the last element

D It alternates between empty and full subsets

💡 Hint

Refer to key_moments about backtracking and step 15 in execution_table.

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 == length, add current subset to result
- Backtrack by removing last added element after recursion
- Result contains all 2^n subsets

Full Transcript

This visualization shows how to generate all subsets of a set using recursion. We start with an empty subset and at each element, we decide to include or exclude it. The recursion explores both choices, building subsets step by step. When we reach the end of the list, we add the current subset to the result. We then backtrack by removing the last element to explore other possibilities. The execution table tracks each step, showing the current index, subset, and subsets collected so far. Key moments clarify why subsets are added only at the end and why backtracking is necessary. The quiz tests understanding of the recursion flow and backtracking effect.

Practice

1. What does the term powerset mean in the context of subsets?

easy

A. Only the subsets with even number of elements

B. All possible subsets of a given set including empty and full set

C. Subsets that contain only one element

D. Subsets that exclude the empty set

Solution

1. Step 1: Understand the definition of powerset

   The powerset of a set is the collection of all 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 subsets of fixed size
• Ignoring the full set as a subset

2. Which of the following C# code snippets correctly initializes an empty list of subsets for generating a powerset?

easy

A. var subsets = new List();

B. var subsets = new List<int>();

C. var subsets = new List();

D. var subsets = new List<int>(); subsets.Add(new List<int>());

Solution

1. Step 1: Identify the correct data structure for subsets

   Each subset is a list of integers, so the collection of subsets should be a list of lists of integers.

2. Step 2: Check each option's type

   var subsets = new List(); uses List, which is correct. var subsets = new List<int>(); is List<int> (single list), var subsets = new List(); is List (array instead of list), var subsets = new List<int>(); subsets.Add(new List<int>()); mixes types incorrectly.

3. Final Answer:

   var subsets = new List(); -> Option A

4. Quick Check:

   List of list<int> for subsets [OK]

Hint: Use List to hold all subsets [OK]

Common Mistakes:

• Using List<int> instead of List
• Confusing arrays with lists
• Adding elements before initializing list

3. What is the output of the following C# code snippet?

var nums = new int[] {1, 2};
var subsets = new List { new List<int>() };
foreach (var num in nums) {
  int count = subsets.Count;
  for (int i = 0; i < count; i++) {
    var newSubset = new List<int>(subsets[i]) { num };
    subsets.Add(newSubset);
  }
}
foreach (var subset in subsets) {
  Console.Write(string.Join(",", subset) + "|");
}

medium

A. | |1|2|

B. |1|2|1,2|

C. | |1|2|1,2|

D. |1|2|

Solution

1. Step 1: Trace initial subsets list

   Initially subsets contains one empty list: [[]].

2. Step 2: Process first number 1

   For num=1, we add subsets: [1] to subsets. Now subsets = [[], [1]].

3. Step 3: Process second number 2

   For num=2, we add subsets: [2] and [1,2]. Now subsets = [[], [1], [2], [1,2]].

4. Step 4: Print all subsets

   Empty subset prints as "|", so output is "| |1|2|1,2|".

5. Final Answer:

   | |1|2|1,2| -> Option C

6. Quick Check:

   All subsets printed with empty first [OK]

Hint: Empty subset prints as empty string before others [OK]

Common Mistakes:

• Ignoring empty subset in output
• Not copying subsets before adding new element
• Miscounting subsets during iteration

4. Identify the error in the following C# code for generating subsets:

var nums = new int[] {1, 2};
var subsets = new List();
foreach (var num in nums) {
  int count = subsets.Count;
  for (int i = 0; i < count; i++) {
    var newSubset = new List<int>(subsets[i]) { num };
    subsets.Add(newSubset);
  }
}

medium

A. subsets list is not initialized with empty subset

B. Using List<int> instead of List

C. Incorrect loop range in inner for loop

D. Adding elements to subsets inside foreach causes runtime error

Solution

1. Step 1: Check initialization of subsets

   subsets is empty initially, so count is 0 and inner loop never runs.

2. Step 2: Understand consequence

   Without starting with empty subset, no new subsets are generated.

3. Final Answer:

   subsets list is not initialized with empty subset -> Option A

4. Quick Check:

   Empty subset needed to start [OK]

Hint: Always start subsets with empty list to generate powerset [OK]

Common Mistakes:

• Not adding empty subset before loop
• Assuming subsets auto-initialize
• Modifying list while iterating without base case

5. Given a list nums = new List<int> {1, 2, 2}, which modification to the standard powerset generation code will correctly generate all unique subsets without duplicates?

hard

A. Use a HashSet to store subsets as strings to avoid duplicates

B. Add all subsets without any check; duplicates will be filtered later

C. Use a Dictionary to map counts and generate subsets

D. Sort nums and skip adding duplicate elements in inner loop

Solution

1. Step 1: Understand duplicate problem

   Input has duplicates (2 appears twice), so normal powerset code generates duplicate subsets.

2. Step 2: Identify correct approach

   Sorting nums allows skipping duplicates during subset generation to avoid repeated subsets.

3. Step 3: Evaluate options

   Sort nums and skip adding duplicate elements in inner loop correctly describes sorting and skipping duplicates. Use a HashSet to store subsets as strings to avoid duplicates is workaround but less efficient. Add all subsets without any check; duplicates will be filtered later allows duplicates. Use a Dictionary to map counts and generate subsets is unrelated.

4. Final Answer:

   Sort nums and skip adding duplicate elements in inner loop -> Option D

5. Quick Check:

   Sort and skip duplicates to avoid repeats [OK]

Hint: Sort input and skip duplicates while generating subsets [OK]

Common Mistakes:

• Not sorting input before generating subsets
• Trying to remove duplicates after generation
• Using complex data structures unnecessarily