Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,2], a solution is:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
78. Subsets 的拓展，这题数组里面可能含有重复元素。
Python：
class Solution(object):
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
result = [[]]
previous_size = 0
for i in xrange(len(nums)):
size = len(result)
for j in xrange(size):
# Only union non-duplicate element or new union set.
if i == 0 or nums[i] != nums[i - 1] or j >= previous_size:
result.append(list(result[j]))
result[-1].append(nums[i])
previous_size = size
return result
Python:
class Solution2(object):
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
result = []
i, count = 0, 1 << len(nums)
nums.sort() while i < count:
cur = []
for j in xrange(len(nums)):
if i & 1 << j:
cur.append(nums[j])
if cur not in result:
result.append(cur)
i += 1 return result
Python:
class Solution3(object):
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
result = []
self.subsetsWithDupRecu(result, [], sorted(nums))
return result def subsetsWithDupRecu(self, result, cur, nums):
if not nums:
if cur not in result:
result.append(cur)
else:
self.subsetsWithDupRecu(result, cur, nums[1:])
self.subsetsWithDupRecu(result, cur + [nums[0]], nums[1:])
C++：
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int> &nums) {
vector<vector<int>> result(1);
sort(nums.begin(), nums.end());
size_t previous_size = 0;
for (size_t i = 0; i < nums.size(); ++i) {
const size_t size = result.size();
for (size_t j = 0; j < size; ++j) {
// Only union non-duplicate element or new union set.
if (i == 0 || nums[i] != nums[i - 1] || j >= previous_size) {
result.emplace_back(result[j]);
result.back().emplace_back(nums[i]);
}
}
previous_size = size;
}
return result;
}
};
类似题目：