Subsets (Power Set)

Generate all possible subsets of a set of unique integers.

10 min read

Time: O(n)

Space: O(1)

Solve on LeetCode

Problem Understanding

Given an integer array nums of unique elements, return all possible subsets (the power set).

Example: nums = [1, 2, 3]

Output: [], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]

There should be $2^N$ subsets.

Algorithm Strategy

We can use the Choose/Not Choose pattern.

For each element in the array, we have exactly two choices:

Include it in the current subset.
Exclude it from the current subset.

We iterate from index 0 to n. At each index, we branch into these two possibilities.

Interactive Visualization

Step 1 / 1

Empty Heap

Initializing...

Custom Input

Watch how the tree expands. Each level represents an index in nums.

Try clicking 'Randomize' to see how the tree changes with different input arrays.

Dry Run

nums = [1, 2]

Index	Current Subset	Decision	Resulting State
0	`[]`	Include 1	`dfs(i=1, sub=[1])`
1	`[1]`	Include 2	`dfs(i=2, sub=[1, 2])`
2	`[1, 2]`	Base Case	Add [1, 2]
1	`[1]`	Backtrack	Pop 2 -> `[1]`
1	`[1]`	Exclude 2	`dfs(i=2, sub=[1])`
2	`[1]`	Base Case	Add [1]
0	`[]`	Backtrack	Pop 1 -> `[]`
0	`[]`	Exclude 1	`dfs(i=1, sub=[])`
1	`[]`	Include 2	`dfs(i=2, sub=[2])`
2	`[2]`	Base Case	Add [2]

Edge Cases & Common Mistakes

Watch out for these pitfalls:

Empty Input: nums = [] should return [[]], not [].
Duplicate Elements: This specific problem assumes unique elements. If duplicates were allowed (Subsets II), you would need to sort and skip duplicates to avoid generating the same subset twice.
Reference Trap: A very common bug in Java/Python is adding the current list reference to result. Since current keeps changing, your final result will be a list of empty lists. Always use new ArrayList<>(current) or subset.copy().

Solution

Standard Backtracking implementations.

1class Solution:
2    def subsets(self, nums: List[int]) -> List[List[int]]:
3        res = []
4        subset = []
5        
6        def dfs(i):
7            if i >= len(nums):
8                res.append(subset.copy())
9                return
10            
11            # Decision 1: Include nums[i]
12            subset.append(nums[i])
13            dfs(i + 1)
14            
15            # Decision 2: Exclude nums[i]
16            subset.pop()
17            dfs(i + 1)
18            
19        dfs(0)
20        return res

Complexity Analysis

Time Complexity: O(N * 2^N). There are $2^N$ subsets, and each can take O(N) to copy/generate.
Space Complexity: O(N) for recursion stack.