题目描述：
给出一个整数数组nums，长度为 $ n $ ，数组中的可能包含重复元素。返回该数组所有可能的子集。
解集中不能包含重复的子集。可以按照任意顺序返回解集。
数据范围：
$ 1\le n \le 10 $
题解：
类似47.全排列II这个问题。只需要排序，然后对于重复的数字，依次从左往右取数。与全排列不同的是，如果当前的数不能取直接跳到下一个数。
使用二进制枚举时，如果一个二进制数，存在不按顺序取数行为，直接跳过该二进制数。
代码：
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
29
30
31
32
33
34
35
36
37
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
vector<vector<int>> ans;
void dfs(int step, vector<int> &nums, vector<int> &cur, vector<bool> &vis)
{
if (step == nums.size())
{
ans.emplace_back(cur);
return;
}
if (step > 0 && nums[step] == nums[step - 1] && !vis[step - 1])
{
dfs(step + 1, nums, cur, vis);
}
else
{
cur.emplace_back(nums[step]);
vis[step] = true;
dfs(step + 1, nums, cur, vis);
vis[step] = false;
cur.pop_back();
dfs(step + 1, nums, cur, vis);
}
}
vector<vector<int>> subsetsWithDup(vector<int> &nums)
{
vector<bool> vis(nums.size(), false);
vector<int> cur;
sort(nums.begin(), nums.end());
dfs(0, nums, cur, vis);
return ans;
}
};
|