78. Subsets
Category: /leetcodeLeetcode Link | Backtrack template
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:
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Example 2:
Input: nums = [0]
Output: [[],[0]]
Constraints:
1 <= nums.length <= 10
-10 <= nums[i] <= 10
All the numbers of nums are unique.
Solution
- Backtrack 模板解法 T: O(2^N), S: O(N)
def subsets(nums):
res = []
track = []
backtrack(nums, 0, track)
return res
def backtrack(nums, start, track):
res.append(track)
for i in range(start, len(nums)):
track.append(nums[i]) # make choice
backtrack(nums, i+1, track)
track.pop() # undo choice
run simulation:
res:
[[]]
[[], [1]]
[[], [1], [1, 2]],
[[], [1], [1, 2], [1, 2, 3]]
[[], [1], [1, 2], [1, 2, 3], [1, 3]]
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2]]
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3]]
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
- Recursive is easier to understand, but Time complexity is worse: T: O(N*2^N), S: O(N)
Idea: A + [[nums[i] + A[i] for i in range(len[A])]
