# [C++]Using Map with 6ms

• ``````class Solution {
private:
vector<pair<int, int>> list;
vector<int> sol;
vector<vector<int>> res;
void backtrack(int cur) {
for (int i = cur; i < list.size(); i++) {
if (list[i].second > 0) {
sol.push_back(list[i].first);
res.push_back(sol);
list[i].second--;
backtrack(i);
sol.pop_back();
list[i].second++;
}
}
}
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
map<int, int> count;
for (int i = 0; i < nums.size(); i++)
count[nums[i]]++;
for (auto x: count)
list.push_back(make_pair(x.first, x.second));
res.push_back(vector<int>(0));
backtrack(0);
return res;
}
};
``````

using map to count the number of a value in the array. So you don't have to compare list[i] with list[i-1] since they are different in the `vector<pair<int, int>> list`. Maybe a tree would help understand:
given[1, 2, 2, 3]

``````           [  empty  ]   <---add[]
/       |    \
1         2     3    <---add[1], [2], [3]
/   \      /  \
2      3    2    3   <---add[1, 2], [1, 3], [2, 2], [2, 3]
/  \         |
2    3        3   <---add[1, 2, 2], [1, 2, 3], [2, 2, 3]
|
``````

The output sequence is not layer-based, but depth-based. My poor English...

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