# 8ms C++ solution, easy to understand

• The idea is to first remove the duplicates (keeping record of the number of duplicates) and then perform a DFS. For example, for `nums = [5, 6, 6]`, we first remove the duplicates and get `sinNums = [5, 6]`, `dups = [1, 2]` (meaning that 5 appears once and 6 appears twice). After that, the following DFS is performed:

path = [] -> [5] -> [5, 6] -> [5, 6, 6] -> [6] -> [6, 6]

``````class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
if (nums.size() == 0)
return vector<vector<int>>();
vector<int> path;
vector<vector<int>> res(1, path);
sort(nums.begin(), nums.end());
vector<int> sinNums(1, nums[0]), dups(1, 1);
for (int i = 1; i < nums.size(); i++)
if (nums[i] != nums[i - 1])
sinNums.push_back(nums[i]), dups.push_back(1);
else
dups[dups.size() - 1]++;
__subsetsWithDup(sinNums, dups, res, path, 0);
return res;
}

private:
void __subsetsWithDup(vector<int>& nums, vector<int>& dups, vector<vector<int>>& res, vector<int>& path, int pos) {
for (int j = pos; j < nums.size(); j++) {
int count = 0;
for (int i = 0; i < dups[j]; i++) {
path.push_back(nums[j]);
res.push_back(path);
__subsetsWithDup(nums, dups, res, path, j + 1);
count++;
}
path.erase(path.end() - count, path.end());
}
return ;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.