Complexity Analysis
def subsets(nums):
result = [[]]
for x in nums:
result += [s + [x] for s in result]
return resultWhat is the time and space complexity?
Work it out before scrolling down.
Time
O(n × 2ⁿ)
Space
O(n × 2ⁿ)
How to derive it
After processing element i, result has 2^i subsets. For each new element, we copy all existing subsets and add the element → doubling the list each time. Total subsets: 2ⁿ, each up to length n. Copying and creating them takes O(n × 2ⁿ). The output itself is O(n × 2ⁿ). This is inherent — there are 2ⁿ subsets to enumerate.