My algorithm is adapted from an iterative algorithm of the Subset puzzle.

Although this is not the best algorithm for this puzzle, compare to another one, I still want to share it.

Instead of taking one number as a basic unit, I use one set of identical numbers as the basic unit. When I see `1,2,2`

, I think about `[1],[2],[2,2]`

.

Every time, I insert a few identical numbers into the old subsets. If the last number of the subset is identical to the current numbers, just skip, so as to avoid duplicates.

```
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int> &S) {
vector<int> set = S;
sort(set.begin(), set.end()); // now the numbers are in ascending order
vector<int> counts(set.size(), 1);
vector<vector<int>> superset = {{}};
for (int i = 0; i < set.size(); i++) {
if (i > 0 && set[i-1] == set[i]) {
counts[i] = counts[i-1] + 1; // the nth-identical number
}
int size = superset.size();
for (int j = 0; j < size; j++) {
if (!superset[j].empty() && superset[j].back() == set[i]) {
continue; // [x], [x,x], ..., [x,x,...] conflict with each other
}
vector<int> subset = superset[j];
//subset.reserve(subset.size() + counts[i]);
for (int k = 0; k < counts[i]; k++) {
subset.push_back(set[i]);
}
superset.push_back(subset);
}
}
return superset;
}
};
```