90 Subsets II
Given a collection of integers that might contain duplicates, nums, return all possible subsets.
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],
[]
]
The Idea: Implement the power set recursive formula, with the added benefit of ignoring duplicates. Duplicates can be used if we first sort the vector, and then append to an
unordered_set. Sorting the vector essentially renders the ordering the vector obsolete, and the unordered_setavoids direct duplication.The powerset begins with the empty set, and the build across each set by appending a character to end of each set.
case 1: {} = P(0) (empty set); 2^0 = 1
case 2: {}, {a} = P('a'); 2^1 = 2
case n: {}, {a}, {b}, {ab} = P('ab'); 2^2 = 4
' '
' ' a
' ' a b ab
' ' a b ab c ac bc abc
' ' a b ab c ac bc abc d ad bd abd cd acd bcd abcd
Complexity: O(n^2) time and space
struct VectorHash {
size_t operator()(const std::vector<int>& v) const {
std::hash<int> hasher;
size_t seed = 0;
for (int i : v) {
seed ^= hasher(i) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
return seed;
}
};
vector<vector<int>> subsetsWithDup(vector<int> &nums) {
sort(nums.begin(), nums.end());
unordered_set<vector<int>, VectorHash> unique_set;
unique_set.reserve(1 << nums.size()); // pow(2, nums.size())
unique_set.insert(vector<int>());
for (int i = 1; i <= nums.size(); i++) {
int cur_size = unique_set.size();
unordered_set<vector<int>, VectorHash> unique_set_cp = unique_set;
for (auto &v : unique_set_cp) {
vector<int> next = v;
next.push_back(nums.at(i - 1));
unique_set.insert(next);
}
}
vector<vector<int>> unique_subsets;
unique_subsets.reserve(1 << nums.size());
for (auto &v : unique_set)
unique_subsets.push_back(v);
return unique_subsets;
}
Testing
int main()
{
//vector<int> t1 = { 1,2,2 };
//print2d(subsetsWithDup(t1));
//vector<int> t2 = { 1,2,3 };
//print2d(subsetsWithDup(t2));
vector<int> t3 = { 4, 4, 4, 1, 4 };
print2d(subsetsWithDup(t3));
}
Last modified 4yr ago