78. Subsets
## description
## 78. Subsets
Given an integer array nums of unique elements, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1:
1Input: nums = [1,2,3]
2Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]Example 2:
1Input: nums = [0]
2Output: [[],[0]]- –1 <= nums.length <= 10
- –-10 <= nums[i] <= 10
- –All the numbers of nums are unique.
Constraints:
## notes
### Intuition
At each element, there are exactly two choices: include it in the current subset or skip it. Backtracking explores both branches at every position, naturally generating all 2^n subsets.
### Implementation
Use a recursive recurse(i) with a shared subset list and res list. Base case: when i >= len(nums), append a copy of subset to res. Otherwise, add nums[i] to subset and recurse (include branch), then pop it and recurse again (exclude branch)—both advancing to i + 1.
### Edge-cases
The empty set is handled naturally—it's added when all elements take the exclude branch. No duplicate handling is needed since the problem guarantees unique elements.
- –Time: O(n 2^n): 2^n subsets, each taking up to O(n) to copy
- –Space: O(n): recursion depth and the current subset list, excluding output
### Complexity
## solution
1from typing import List
2
3class Solution:
4 def subsets(self, nums: List[int]) -> List[List[int]]:
5 res = []
6 subset = []
7 def recurse(i):
8 if i >= len(nums):
9 res.append(subset.copy())
10 return
11 subset.append(nums[i])
12 recurse(i + 1)
13 subset.pop()
14 recurse(i + 1)
15
16 recurse(0)
17 return res
18
19
20if __name__ == "__main__":
21 # Include one-off tests here or debugging logic that can be run by running this file
22 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
23 solution = Solution()
24