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

↓

More elements?

Yes→Repeat choices

No↓

Done: All subsets generated

Start with an empty subset and for each element, choose to include or exclude it, building all possible subsets step-by-step.

Execution Sample

DSA C++

void generateSubsets(vector<int>& nums, int index, vector<int>& current, vector<vector<int>>& result) {
  if (index == nums.size()) {
    result.push_back(current);
    return;
  }
  // Exclude current element
  generateSubsets(nums, index + 1, current, result);
  // Include current element
  current.push_back(nums[index]);
  generateSubsets(nums, index + 1, current, result);
  current.pop_back();
}

This recursive function builds all subsets by including or excluding each element in the input list.

Execution Table

Step	Operation	Current Index	Current Subset	Result Subsets	Action
1	Start recursion	0	[]	[]	Begin with empty subset
2	Exclude element 1	1	[]	[]	Do not add nums[0]
3	Exclude element 2	2	[]	[]	Do not add nums[1]
4	Exclude element 3	3	[]	[[]]	Reached end, add []
5	Include element 3	3	[3]	[[], [3]]	Add nums[2] and add subset
6	Backtrack after include 3	2	[]	[[], [3]]	Remove nums[2]
7	Include element 2	2	[2]	[[], [3]]	Add nums[1]
8	Exclude element 3	3	[2]	[[], [3]]	Do not add nums[2]
9	Add subset	3	[2]	[[], [3], [2]]	Add current subset
10	Include element 3	3	[2, 3]	[[], [3], [2]]	Add nums[2]
11	Add subset	3	[2, 3]	[[], [3], [2], [2, 3]]	Add current subset
12	Backtrack after include 3	2	[2]	[[], [3], [2], [2, 3]]	Remove nums[2]
13	Backtrack after include 2	1	[]	[[], [3], [2], [2, 3]]	Remove nums[1]
14	Include element 1	1	[1]	[[], [3], [2], [2, 3]]	Add nums[0]
15	Exclude element 2	2	[1]	[[], [3], [2], [2, 3]]	Do not add nums[1]
16	Exclude element 3	3	[1]	[[], [3], [2], [2, 3]]	Do not add nums[2]
17	Add subset	3	[1]	[[], [3], [2], [2, 3], [1]]	Add current subset
18	Include element 3	3	[1, 3]	[[], [3], [2], [2, 3], [1]]	Add nums[2]
19	Add subset	3	[1, 3]	[[], [3], [2], [2, 3], [1], [1, 3]]	Add current subset
20	Backtrack after include 3	2	[1]	[[], [3], [2], [2, 3], [1], [1, 3]]	Remove nums[2]
21	Include element 2	2	[1, 2]	[[], [3], [2], [2, 3], [1], [1, 3]]	Add nums[1]
22	Exclude element 3	3	[1, 2]	[[], [3], [2], [2, 3], [1], [1, 3]]	Do not add nums[2]
23	Add subset	3	[1, 2]	[[], [3], [2], [2, 3], [1], [1, 3], [1, 2]]	Add current subset
24	Include element 3	3	[1, 2, 3]	[[], [3], [2], [2, 3], [1], [1, 3], [1, 2]]	Add nums[2]
25	Add subset	3	[1, 2, 3]	[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]	Add current subset
26	Backtrack after include 3	2	[1, 2]	[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]	Remove nums[2]
27	Backtrack after include 2	1	[1]	[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]	Remove nums[1]
28	Backtrack after include 1	0	[]	[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]	Remove nums[0]
29	End recursion	0	[]	[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]	All subsets generated

💡 Recursion ends when index reaches size of input array, all subsets collected in result

Variable Tracker

Variable	Start	After Step 14	After Step 21	After Step 24	Final
index	0	1	2	3	0
current subset	[]	[1]	[1, 2]	[1, 2, 3]	[] (backtracked)
result subsets	[]	[[], [3], [2], [2, 3]]	[[], [3], [2], [2, 3], [1], [1, 3]]	[[], [3], [2], [2, 3], [1], [1, 3], [1, 2]]	[[], [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.size()?

Because only when we have considered all elements (index == size) do we have a complete subset to add, as shown in execution_table rows 4, 5, 9, 11, 17, 19, 23, 25.

Why do we backtrack by removing the last element after including it?

To restore the subset to its previous state before exploring other choices, as seen in steps 6, 12, 20, 26, and 27 where current subset elements are popped.

How does the recursion explore all subsets without missing any?

Because at each step it branches into two: including or excluding the current element, covering all combinations, demonstrated by the two recursive calls at each index in the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 10, what is the current subset?

A [1, 3]

B [2, 3]

C [1, 2]

D [3]

💡 Hint

Check the 'Current Subset' column at step 10 in the execution_table.

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

A Step 4

B Step 1

C Step 29

D Step 14

💡 Hint

Look for when '[]' is first added to 'Result Subsets' in the execution_table.

If we remove the backtracking pop_back() call, what will happen to the subsets generated?

A Subsets will be duplicated

B Subsets will be the same

C Subsets will be incomplete and incorrect

D Recursion will not terminate

💡 Hint

Refer to key_moments about backtracking and execution_table steps where pop_back() occurs.

Concept Snapshot

Generate All Subsets (Powerset):
- Use recursion with index to track position
- At each step, choose to include or exclude current element
- Add subset to result when index == nums.size()
- Backtrack by removing last element after including
- Result contains all 2^n subsets

Full Transcript

This visualization shows how to generate all subsets of a list using recursion. We start with an empty subset and at each element, we decide to include or exclude it. When we reach the end of the list, we add the current subset to the result. We backtrack after including an element to explore other possibilities. The execution table traces each step, showing the current index, subset, and result. Key moments explain why subsets are added only at the end and why backtracking is necessary. The quiz tests understanding of subset states and recursion flow.

Practice

1. What does the "Generate All Subsets (Powerset)" algorithm produce when given a set {1, 2}?

easy

A. Only subsets with two elements: {1, 2}

B. All possible subsets including empty set: {}, {1}, {2}, {1, 2}

C. Only subsets with one element: {1}, {2}

D. Only the empty set: {}

Solution

1. Step 1: Understand what subsets mean

   Subsets include all combinations of elements, from empty to full set.

2. Step 2: List all subsets of {1, 2}

   They are {}, {1}, {2}, and {1, 2}.

3. Final Answer:

   All possible subsets including empty set: {}, {1}, {2}, {1, 2} -> Option B

4. Quick Check:

   Subsets = all combinations [OK]

Hint: Remember powerset includes empty and full sets [OK]

Common Mistakes:

• Thinking subsets only have full or single elements
• Ignoring the empty subset
• Confusing subsets with permutations

2. Which of the following C++ code snippets correctly initializes an empty vector of vectors to store subsets?

easy

A. std::vector<int> subsets;

B. std::vector subsets = {{}};

C. std::vector subsets;

D. std::vector subsets<int>;

Solution

1. Step 1: Identify correct vector declaration

   We need a vector of vectors of int to store subsets.

2. Step 2: Check syntax correctness

   std::vector subsets; uses correct syntax: std::vector subsets; initializes empty vector of vectors.

3. Final Answer:

   std::vector subsets; -> Option C

4. Quick Check:

   Correct vector of vectors syntax [OK]

Hint: Use vector for subsets storage [OK]

Common Mistakes:

• Using vector<int> instead of vector
• Incorrect template syntax like vector subsets<int>
• Trying to initialize with empty braces incorrectly

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

std::vector<int> nums = {1, 2};
std::vector subsets = {{}};
for (int num : nums) {
    int n = subsets.size();
    for (int i = 0; i < n; i++) {
        std::vector<int> newSubset = subsets[i];
        newSubset.push_back(num);
        subsets.push_back(newSubset);
    }
}
for (auto &subset : subsets) {
    for (int x : subset) std::cout << x << " ";
    std::cout << "| ";
}

medium

A. | | 1 | 2 | 1 2 |

B. | | 1 2 | 1 | 2 |

C. | 1 | 2 | 1 2 |

D. | 1 2 | 1 | 2 |

Solution

1. Step 1: Understand initial subsets and loop

   Initially subsets = {{}}, empty subset only. For each num, we add new subsets by adding num to existing subsets.

2. Step 2: Trace iterations

   For num=1: subsets become {}, {1}. For num=2: subsets become {}, {1}, {2}, {1, 2}.

3. Final Answer:

   | | 1 | 2 | 1 2 | -> Option A

4. Quick Check:

   All subsets printed with spaces and separators [OK]

Hint: Start with empty subset and add elements iteratively [OK]

Common Mistakes:

• Missing the empty subset in output
• Printing subsets in wrong order
• Confusing push_back inside loop

4. Identify the error in this C++ code snippet for generating subsets:

std::vector<int> nums = {1, 2};
std::vector subsets;
for (int num : nums) {
    int n = subsets.size();
    for (int i = 0; i < n; i++) {
        std::vector<int> newSubset = subsets[i];
        newSubset.push_back(num);
        subsets.push_back(newSubset);
    }
}

medium

A. subsets vector is not initialized with empty subset before loop

B. Loop variable i should start from 1, not 0

C. newSubset.push_back(num) should be outside inner loop

D. nums vector should be empty to generate subsets

Solution

1. Step 1: Check initialization of subsets

   subsets is empty initially, so subsets.size() is 0, inner loop never runs.

2. Step 2: Identify missing empty subset

   We must start subsets with empty subset {{}} to build new subsets correctly.

3. Final Answer:

   subsets vector is not initialized with empty subset before loop -> Option A

4. Quick Check:

   Empty subset needed to start building subsets [OK]

Hint: Always start subsets with empty subset {{}} [OK]

Common Mistakes:

• Not initializing subsets with empty subset
• Changing loop start index incorrectly
• Misplacing push_back calls

5. Given a vector nums = {1, 2, 2}, which code modification ensures the generated subsets contain no duplicate subsets?

hard

A. Generate subsets normally; duplicates are impossible with vector<int>.

B. Use a set to store subsets after generation to remove duplicates.

C. Ignore duplicate elements in nums vector before generating subsets.

D. Sort nums first and skip adding duplicates during subset generation.

Solution

1. Step 1: Understand duplicates in input

   Input has duplicate 2's, so subsets like {2} can appear multiple times.

2. Step 2: Use sorting and skip duplicates

   Sorting nums helps detect duplicates; skip adding subsets with same element consecutively to avoid duplicates.

3. Final Answer:

   Sort nums first and skip adding duplicates during subset generation. -> Option D

4. Quick Check:

   Sorting + skipping duplicates avoids repeated subsets [OK]

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

Common Mistakes:

• Assuming duplicates never occur
• Removing duplicates from input loses valid subsets
• Using set after generation is less efficient