Subsets

Overview

Generate all possible subsets (the power set) of a given array. Each subset can have any length from 0 to n.

Example: [1,2] → [], [1], [2], [1,2]

---

Iterative Approach

Instead of recursion, build results iteratively by extending existing combinations.

Subsets Without Duplicates

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = [[]]
        for num in nums:
            ans += [cur + [num] for cur in ans]
        return ans

Logic: For each new number, duplicate all existing subsets and append the number to each copy.

Example: [1,2]

Step 0: [[]]
Step 1: [[], [1]]  (append 1 to [])
Step 2: [[], [1], [2], [1,2]]  (append 2 to [] and [1])

---

Subsets With Duplicate Handling

When duplicates exist, we must control when we extend each subset to avoid creating duplicate results.

Key Insight

After sorting, duplicates are adjacent. For each duplicate value, only extend subsets created in the previous iteration of that value.

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        ans = [[]]
        nums.sort()
        start = end = 0
        
        for i in range(len(nums)):
            # If duplicate, only extend subsets from previous step
            start = end if i > 0 and nums[i] == nums[i-1] else 0
            end = len(ans)
            
            # Only extend subsets created in the previous iteration
            for j in range(start, end):
                ans.append(ans[j] + [nums[i]])
        
        return ans

Tip

The start pointer ensures duplicates only extend subsets generated in the previous step for the value, preventing duplicate subset generation without needing a set.

Duplicate Handling Explained

Before sort: [4, 4, 9, 9, 9]
After sort: [4, 4, 9, 9, 9]

Initial: [[]]

i=0, nums[0]=4 (first time):
  start=0, end=1
  Extend from all subsets: [[], [4]]

i=1, nums[1]=4 (duplicate):
  start=1 (only extend from subsets created last iteration)
  end=2
  Extend [4] only: [[], [4], [4,4]]
  ✓ Only one [4] carries forward — avoiding duplicates

i=2, nums[2]=9 (first time):
  start=0, end=3
  Extend from all: [[], [4], [4,4], [9], [4,9], [4,4,9]]

i=3, nums[3]=9 (duplicate):
  start=3, end=6
  Extend from subsets created last iteration only
  Result: add [9,9], [4,9,9], [4,4,9,9]

i=4, nums[4]=9 (duplicate):
  start=6, end=9
  Extend from subsets created in previous 9 iteration only

---

Complexity Analysis

Time: O(n × 2^n) — total number of subsets is 2^n, and each takes up to O(n) to construct

Space: O(n × 2^n) — storing all subsets (each subset can be up to size n)

Summary

Each element doubles the number of subsets.
Duplicates don’t change the count — they only restrict where new subsets are allowed to grow from.