Generate All Subsets Powerset in DSA Python - 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 choose to include or exclude it, building all possible subsets step-by-step.

Execution Sample

DSA Python

def powerset(nums):
    result = []
    def backtrack(i, path):
        if i == len(nums):
            result.append(path[:])
            return
        backtrack(i+1, path + [nums[i]])
        backtrack(i+1, path)
    backtrack(0, [])
    return result

This code generates all subsets of the list nums by recursively including or excluding each element.

Execution Table

Step	Operation	Index i	Current Path	Action	Resulting Subsets
1	Start recursion	0	[]	Call backtrack(0, [])	[]
2	Include nums[0]=1	1	[1]	Call backtrack(1, [1])	[]
3	Include nums[1]=2	2	[1, 2]	Call backtrack(2, [1, 2])	[]
4	Include nums[2]=3	3	[1, 2, 3]	Reached end, add [1, 2, 3]	[[1, 2, 3]]
5	Exclude nums[2]=3	3	[1, 2]	Reached end, add [1, 2]	[[1, 2, 3], [1, 2]]
6	Exclude nums[1]=2	2	[1]	Call backtrack(2, [1])	[[1, 2, 3], [1, 2]]
7	Include nums[2]=3	3	[1, 3]	Reached end, add [1, 3]	[[1, 2, 3], [1, 2], [1, 3]]
8	Exclude nums[2]=3	3	[1]	Reached end, add [1]	[[1, 2, 3], [1, 2], [1, 3], [1]]
9	Exclude nums[0]=1	1	[]	Call backtrack(1, [])	[[1, 2, 3], [1, 2], [1, 3], [1]]
10	Include nums[1]=2	2	[2]	Call backtrack(2, [2])	[[1, 2, 3], [1, 2], [1, 3], [1]]
11	Include nums[2]=3	3	[2, 3]	Reached end, add [2, 3]	[[1, 2, 3], [1, 2], [1, 3], [1], [2, 3]]
12	Exclude nums[2]=3	3	[2]	Reached end, add [2]	[[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2]]
13	Exclude nums[1]=2	2	[]	Call backtrack(2, [])	[[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2]]
14	Include nums[2]=3	3	[3]	Reached end, add [3]	[[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3]]
15	Exclude nums[2]=3	3	[]	Reached end, add []	[[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]
16	End recursion	-	-	All subsets generated	[[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]

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

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 8	After Step 12	After Step 15	Final
i	0	1	3	3	3	3	3
path	[]	[1]	[1, 2, 3]	[1]	[2]	[]	[]
result	[]	[]	[[1, 2, 3]]	[[1, 2, 3], [1, 2], [1, 3], [1]]	[[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2]]	[[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]	[[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]

Key Moments - 3 Insights

Why do we add the current path to the result only when i equals the length of nums?

Because only when we have considered all elements (i == len(nums)) do we have a complete subset to add, as shown in steps 4, 5, 7, 8, 11, 12, 14, 15 in the execution_table.

Why do we call backtrack twice at each step?

Each call represents a choice: one includes the current element, the other excludes it. This ensures all subsets are explored, as seen in steps 2 and 9, 3 and 6, etc.

Why does the path sometimes get longer and sometimes shorter?

Because when we include an element, we add it to the path (making it longer), and when we exclude, we keep the path as is (shorter). This is visible in the path changes across steps in the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what subset is added to the result?

A [1, 3]

B [1, 2, 3]

C [1, 2]

D [1]

💡 Hint

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

At which step does the recursion first exclude the element nums[0]?

A Step 9

B Step 2

C Step 6

D Step 13

💡 Hint

Look for the first call backtrack with path [] after including nums[0] in the execution_table.

If we change the input list to have 2 elements instead of 3, how many subsets will the final result have?

A 2

B 3

C 4

D 8

💡 Hint

Number of subsets is 2^n, where n is the number of elements; check the final result count in variable_tracker.

Concept Snapshot

Generate All Subsets (Powerset):
- Use recursion with index i and current path.
- At each step, choose to include or exclude nums[i].
- When i == len(nums), add path to result.
- Result contains all subsets, total 2^n subsets.
- Backtracking explores all combinations systematically.

Full Transcript

This visualization shows how to generate all subsets of a list using recursion and backtracking. We start with an empty subset and at each element, we decide to include or exclude it. This creates two recursive calls per element, exploring all combinations. When we reach the end of the list, we add the current subset to the result. The execution table tracks each step, showing the current index, path, and subsets collected. The variable tracker shows how variables change over time. Key moments clarify why subsets are added only at the end and why two recursive calls happen at each step. The quiz tests understanding of the recursion steps and subset counts. This method produces all 2^n subsets of the input list.

Practice

1. What does the powerset of a set represent in terms of subsets?

easy

A. Only subsets with even number of elements

B. Only the full set itself

C. Only subsets with odd number of elements

D. All possible subsets including empty and full set

Solution

1. Step 1: Understand the definition of powerset

   The powerset of a set is the collection of all subsets of that set, including the empty set and the set itself.

2. Step 2: Compare options with definition

   All possible subsets including empty and full set correctly states all possible subsets are included. Other options limit subsets incorrectly.

3. Final Answer:

   All possible subsets including empty and full set -> Option D

4. Quick Check:

   Powerset = All subsets [OK]

Hint: Remember powerset means every subset possible [OK]

Common Mistakes:

• Thinking powerset excludes empty set
• Confusing powerset with subsets of certain size
• Assuming powerset only includes full set

2. Which of the following Python code snippets correctly initializes an empty list to store subsets for generating a powerset?

easy

A. subsets = set()

B. subsets = {}

C. subsets = []

D. subsets = ()

Solution

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

   Subsets are typically stored in a list because order and duplicates matter for powerset generation.

2. Step 2: Analyze each option

   subsets = [] uses an empty list []. subsets = {} uses a dictionary {}, which is incorrect. subsets = () uses a tuple (), which is immutable. subsets = set() uses a set(), which cannot store duplicates or ordered subsets.

3. Final Answer:

   subsets = [] -> Option C

4. Quick Check:

   Use list [] for subsets storage [OK]

Hint: Use list [] to store multiple subsets [OK]

Common Mistakes:

• Using {} which creates a dictionary, not a list
• Using () which is immutable tuple
• Using set() which loses order and duplicates

3. What is the output of the following code?

def powerset(nums):
    result = [[]]
    for num in nums:
        result += [curr + [num] for curr in result]
    return result

print(powerset([1, 2]))

medium

A. [[], [1], [1, 2]]

B. [[], [1], [2], [1, 2]]

C. [[1], [2], [1, 2]]

D. [[], [2], [1, 2]]

Solution

1. Step 1: Trace initial result and loop iterations

   Start with result = [[]]. For num=1, add subsets: [] + [1] = [1], so result = [[], [1]]. For num=2, add subsets: [] + [2] = [2], [1] + [2] = [1, 2], so result = [[], [1], [2], [1, 2]].

2. Step 2: Confirm final output list

   The final list contains all subsets: empty, single elements, and full set.

3. Final Answer:

   [[], [1], [2], [1, 2]] -> Option B

4. Quick Check:

   All subsets of [1,2] = [[], [1], [2], [1, 2]] [OK]

Hint: Add new element to all existing subsets each loop [OK]

Common Mistakes:

• Missing empty subset [] in output
• Not combining previous subsets with new element
• Confusing order of subsets

4. Find the error in this powerset generation code:

def powerset(nums):
    result = []
    for num in nums:
        for curr in result:
            result.append(curr + [num])
    return result

print(powerset([1, 2]))

medium

A. result list is empty initially, so loop never runs

B. Appending inside loop modifies list during iteration

C. Missing return statement

D. Using list instead of set causes duplicates

Solution

1. Step 1: Check initial value of result

   result is initialized as empty list []. The inner loop for curr in result will not run because result is empty.

2. Step 2: Understand consequence on output

   Since inner loop never runs, no subsets are added. The function returns empty list [].

3. Final Answer:

   result list is empty initially, so loop never runs -> Option A

4. Quick Check:

   Empty result means no subsets generated [OK]

Hint: Initialize result with [[]] to start with empty subset [OK]

Common Mistakes:

• Not initializing result with [[]]
• Modifying list while iterating (can cause bugs)
• Forgetting to add empty subset initially

5. Given a list nums = [1, 2, 2], which code modification correctly generates the powerset without duplicate subsets?

hard

A. Sort nums and skip duplicates during subset generation

B. Use a set to store tuples of subsets to avoid duplicates

C. Use list comprehension without any checks

D. Remove duplicates from nums before generating subsets

Solution

1. Step 1: Understand the problem with duplicates

   Input has duplicates (2 appears twice). Powerset generation can create duplicate subsets if duplicates are not handled.

2. Step 2: Analyze options for handling duplicates

   Use a set to store tuples of subsets to avoid duplicates uses a set of tuples which works but changes data type and order. Sort nums and skip duplicates during subset generation sorts nums and skips duplicates during recursion, which is standard and efficient. Use list comprehension without any checks ignores duplicates. Remove duplicates from nums before generating subsets removes duplicates, which changes the original set.

3. Final Answer:

   Sort nums and skip duplicates during subset generation -> Option A

4. Quick Check:

   Sort and skip duplicates to avoid repeated subsets [OK]

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

Common Mistakes:

• Removing duplicates changes original data meaning
• Using sets loses subset order
• Ignoring duplicates causes repeated subsets