90. Subsets II
Đề Bài
Given 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
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(n²)
💾 Không gian
O(n)
Lời Giải
Python
0090-subsets-ii.py
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
ans = []
nums.sort()
n = len(nums)
seen = set()
for mask in range(1 << n):
tmp = []
s = ''
for i in range(n):
if not (mask >> i) & 1:
continue
tmp += [nums[i]]
s += str(nums[i])
if s not in seen:
ans += [tmp]
seen.add(s)
return ans