# С++ iterative with O(1) check for duplicates

• Firstly, we sort our nums, then to avoid duplicates:

1. If nums[i-1] != nums[i] we append to every vector with last element less or equal than nums[i]
2. If nums[i-streak-1]==..==nums[i-1] == nums[i] then we have only one vector with all nums[i] "streak+1" times and we want to add nums[i] only to this one

Example:
nums[i-3] == nums[i-2] == nums[i-1] == nums[i] == 2
...
res[i1] = 1, 2 <- skip
res[i2] = 1, 2, 2 <- skip
res[i2] = 1, 2, 2, 2 <- copy and append 2

So we keep track of the current length ("streak" variable + 1) of the sequence and append nums[i] only to the vector that contains all of the previous nums equal to nums[i]

``````  vector<vector<int>> subsetsWithDup(vector<int>& nums)
{
vector<vector<int>> res {{}};

sort(nums.begin(), nums.end());
int streak = 0;

for (int i = 0; i < nums.size(); ++i)
{
if (i && nums[i-1] == nums[i]) ++streak; else streak = 0;

for (int j = res.size(); j--; )
{
auto r = res[j];
if (r.size() && r[r.size()-1] > nums[i]) continue;
if (streak && ( r.size() < streak || r[r.size()-streak] != nums[i])) continue; // the one with all of the previous has r[r.size()-streak] the same as nums[i]

vector<int> ri(r.begin(), r.end());
ri.push_back(nums[i]);
res.push_back(ri);
}
}

return res;
}``````

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