1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> ans;
if (nums.size() != 0) {
vector<int> cur;
sort(nums.begin(), nums.end());
vector<bool> visited(nums.size());
backtrack(ans, cur, nums, 0, visited);
}
return ans;
}
private:
void backtrack(vector<vector<int>>& ans, vector<int>& cur, vector<int>& nums, int start, vector<bool>& visited) {
if (start == nums.size()) {
ans.emplace_back(cur);
return;
}
if (start == 0 || nums[start] != nums[start - 1] || visited[start - 1]) {
cur.emplace_back(nums[start]);
visited[start] = true;
backtrack(ans, cur, nums, start + 1, visited);
visited[start] = false;
cur.pop_back();
}
backtrack(ans, cur, nums, start + 1, visited);
}
};
|