78. Subsets
Medium LeetCodeGiven 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]]
Explanation: All possible subsets of [
1,2,3
] are returned. The empty set [] is also included.
Example 2
Input: nums = [
0
]Output: [[],[0]]
Explanation: The only possible subsets are the empty set [] and the set containing the single element [
0
].
Constraints
1 <= nums.length <= 10
-10 <= nums[i] <= 10
- All the numbers of
nums
are unique
How to solve the problem
- Backtracking (DFS)
python
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
result = []
path = []
def dfs(i):
if i == len(nums):
result.append(path.copy())
return
dfs(i+1)
path.append(nums[i])
dfs(i+1)
path.pop()
dfs(0)
return result
Complexity
- Time complexity: O(K*C(n, k))
- Space complexity: O(K*C(n, k))
Comments
No comments yet. Be the first to comment!