Description
Return every subset of an array of distinct integers, including the empty subset and the complete array. Subset and result order do not matter.
Solution
def subsets(nums):
result = [[]]
for value in nums:
size = len(result)
for i in range(size):
result.append(result[i] + [value])
return resultExamples
Example 1
- Input
[[1,2]]- Output
[[],[1],[2],[1,2]]
Each of the two elements is included or excluded.
Example 2
- Input
[[0]]- Output
[[],[0]]
A one-element array has two subsets.
Example 3
- Input
[[1,2,3]]- Output
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Three choices produce eight subsets.
Approach
Start with the empty subset. For each number, append a copy of every existing subset with that number added; this covers excluding and including it.
Time & space
O(n 2^n) time and O(n 2^n) space for the result, where n is the array length. Aside from output, loop bookkeeping uses O(1) space.