Subsets

Given a list of distinct integers, return all possible subsets (the power set). The result must contain every subset exactly once, including the empty set and the full list, in any order.

Example#

For nums = [1, 2, 3] the answer has 8 subsets: [], [1], [2], [3], [1, 2], [1, 3], [2, 3], and [1, 2, 3]. For nums = [0] the answer is [] and [0].

Brute force note#

You could iterate over all bitmasks from 0 to 2^n minus 1 and read off which elements each mask includes. That works, but the backtracking version generalizes better to variants with duplicates or constraints.

Optimal approach#

Backtrack with a start index. At each call, first record the current path as a valid subset, then extend it by adding each remaining element (from the start index onward) and recursing with the next index. Removing the element after recursion (the undo step) restores the path so the next branch starts clean. Because you always move the start index forward, no subset is generated twice.

 1def subsets(nums):
 2    result = []
 3
 4    def backtrack(start, path):
 5        result.append(path[:])
 6        for i in range(start, len(nums)):
 7            path.append(nums[i])
 8            backtrack(i + 1, path)
 9            path.pop()
10
11    backtrack(0, [])
12    return result
13
14
15print(subsets([1, 2, 3]))
16# [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
17print(subsets([0]))  # [[], [0]]

Complexity#

Time is O(n times 2^n): there are 2^n subsets and copying each path costs up to O(n). Space is O(n) for the recursion depth and path, excluding the output list which holds all subsets.

This is the archetype backtracking enumeration. Study the choose-recurse-undo skeleton there, then continue through the 60-day curriculum.