# Share three methods, collecting from previous discussing(C++)

• ``````//bitmap 12ms
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
n = nums.size();
vector<vector<int>> res(1, vector<int>());
if (n == 0) return res;
sort(nums.begin(), nums.end());
int mask = 0, total = pow(2, n), tmpi, tmpj, lastnum;
bool dp;
for (int i = 1; i < total; i++) {
dp = false;
vector<int> tmp;
lastnum = -1;
for (int j = 0; j < n; j++) {
if (i & (1 << j)) {
//check if duplicate
tmpi = nums[j];
if (nums[j] == lastnum) {
tmpj = j - 1;
while (tmpj >= 0 && nums[tmpj] == lastnum) {
if (!(i & (1 << tmpj))) {
dp = true;
break;
}
tmpj--;
}
}
if (dp) break;
tmp.push_back(tmpi);
}
lastnum = nums[j];
}
if (dp) continue;
res.push_back(tmp);
}

return res;
}

//recursive 8ms
vector<vector<int>> res;
int n;
void generate(vector<int>& num, vector<int>& tmp, int k) {
res.push_back(tmp);
for (int i = k; i < n; i++) {
tmp.push_back(num[i]);
generate(num, tmp, i + 1);
tmp.pop_back();
while (i < n - 1 && num[i] == num[i + 1]) {
i++;
}
}
}

vector<vector<int>> subsetsWithDup3(vector<int>& nums) {
n = nums.size();
vector<int> tmp;
sort(nums.begin(), nums.end());
generate(nums, tmp, 0);
return res;
}

//another recursive 12ms
vector<vector<int>> subsetsWithDup2(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> res(1, vector<int>());
if (n == 0) return res;
sort(nums.begin(), nums.end());
int m, tmpi;
for (int i = 0; i < n; i++) {
tmpi = 1;
while (i - tmpi >= 0 && nums[i - tmpi] == nums[i]) tmpi++;
tmpi--;
m = res.size();
for (int j = 0; j < m; j++) {
if (tmpi > 0 && (res[j].empty() || res[j].size() < tmpi || res[j][res[j].size() - tmpi] != nums[i])) continue;
vector<int> tmp = res[j];
tmp.push_back(nums[i]);
res.push_back(tmp);
}
}
return res;
}``````

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