Subsets

01 · Question

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

02 · Analysis

At index i, branch into taking or skipping nums[i]. Every subset corresponds to one sequence of binary choices, so each appears once. Save a copy at i==n and undo each append. Distinct inputs have 2^n subsets; materializing them takes O(n*2^n) time and output space, plus O(n) auxiliary stack/path space.

03 · Solution

Reference solution

1def subsets(nums: List[int]) -> List[List[int]]:
2    res = []
3    cur = []
4
5    def dfs(i: int) -> None:
6        if i == len(nums):
7            res.append(cur[:])
8            return
9        cur.append(nums[i])
10        dfs(i + 1)
11        cur.pop()
12        dfs(i + 1)
13
14    dfs(0)
15    return res

Unique Paths III

Permutations