90. Subsets II
MediumLeetCodeGiven an integer array nums
that may contain duplicates, 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,2
]Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Example 2
Input: nums = [
0
]Output: [[],[0]]
Constraints
1 <= nums.length <= 10
-10 <= nums[i] <= 10
How to solve the problem
- Backtracking (DFS)
Code
Python
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
path = []
result = []
nums.sort() # Only a sorted list can ensure no duplicated set
def backtracking(startIndex):
result.append(path[:])
coveredSet = set()
for i in range(startIndex, len(nums)):
if nums[i] in coveredSet:
continue
coveredSet.add(nums[i])
path.append(nums[i])
backtracking(i + 1)
path.pop()
backtracking(0)
return result
Complexity
- Time complexity: O(2^n * n)
- Space complexity: O(n)
Comments
No comments yet. Be the first to comment!