Generate All Subsets Powerset in DSA Python

Mental Model

We want to find every possible group of items you can make from a list, including the empty group and the full list.

Analogy: Imagine you have a box of colored beads. You want to see all the different ways you can pick beads from the box, from picking none to picking all of them in every possible combination.

List: [1, 2]
Subsets:
[]
[1]
[2]
[1, 2]

Dry Run Walkthrough

Input: list: [1, 2]

Goal: Find all subsets of the list [1, 2], including empty and full subsets

Step 1: Start with an empty subset []

Subsets: []

Why: We always include the empty subset as a starting point

Step 2: Add 1 to all existing subsets to create new subsets

Subsets: [] and [1]

Why: For each existing subset, adding the new element creates new subsets

Step 3: Add 2 to all existing subsets to create new subsets

Subsets: [], [1], [2], [1, 2]

Why: Repeat the process for the next element to get all combinations

Result:

Subsets: [] -> [1] -> [2] -> [1, 2]

Annotated Code

DSA Python

from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = [[]]  # start with empty subset
        for num in nums:
            new_subsets = []
            for curr in result:
                new_subsets.append(curr + [num])  # add current num to existing subset
            result.extend(new_subsets)  # add new subsets to result
        return result

# Driver code
sol = Solution()
output = sol.subsets([1, 2])
for subset in output:
    print(subset)

result = [[]] # start with empty subset

initialize result with empty subset

for num in nums:

iterate over each number in the input list

for curr in result:

for each existing subset, prepare to add the new number

new_subsets.append(curr + [num]) # add current num to existing subset

create new subset by adding current number

result.extend(new_subsets) # add new subsets to result

add all new subsets to the result list

Output

[]

[1]

[2]

[1, 2]

Complexity Analysis

Time: O(n * 2^n) because for each of the n elements, we double the number of subsets by adding the element to all existing subsets

Space: O(2^n) because the total number of subsets grows exponentially with the number of elements

vs Alternative: This iterative approach is simpler and easier to understand than recursive backtracking but both have similar exponential time and space costs

Edge Cases

empty list []

returns [[]] because the only subset of an empty list is the empty subset

DSA Python

result = [[]]  # start with empty subset

list with one element [5]

returns [] and [5] as subsets

DSA Python

for num in nums:

When to Use This Pattern

When you need to find all possible combinations or groups from a set, use the powerset pattern because it systematically builds every subset.

Common Mistakes

Mistake: Modifying the list of subsets while iterating over it directly
Fix: Create a separate list for new subsets and extend after the loop to avoid infinite loops or missing subsets

Summary

Generates every possible subset of a list including empty and full subsets.

Use when you need to explore all combinations of elements from a set.

The key insight is to build new subsets by adding each element to all existing subsets step-by-step.

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