难度中等1045
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]示例 2：
输入：nums = [0]
输出：[[],[0]]提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10
解题思路：回溯
这道题与 78. 子集 的区别就是这道题的 nums 数组中可能存在重复元素，那么存在重复元素的话就有可能导致我们的结果集会重复，还是一样，与组合问题类似，其发生重复主要是在树层上，而树枝我们是一开始就让其不断的访问下去，回溯后才去访问同一树层，所以在树层才有可能会重复了之前的结果，所以我们这里要做的其实就是将树层访问的时候进行控制，可以参考这道题 40. 组合总和 II ，都是同样的思想！
剩下的都不是大问题，就是回溯三部曲：递归函数的参数、递归终止条件、单层搜索逻辑。这里主要是在参数多了一个 used，并且在单层搜索逻辑中对树层访问进行判断：
- 当 nums[i] nums[i - 1] 的时候说明当前访问的树层与上一个树层的元素相同，那么势必会导致后面的结果集重复（前提是这个 nums 数组排过序！），所以我们用 used[i - 1] false 来判断是否为树层，false肯定是树层，true肯定是树枝，为什么❓❓❓因为这和我们回溯逻辑有关，我们递归前设置为 true，那么递归下去就是去访问树枝，那么就是 true，而当回来的时候由设为 false，然后 i++，访问下一个树层，这样子就是 false 了！
class Solution {
public:
void backtracking(vector<int>& nums, int index, vector<bool>& used)
{
vv.push_back(v); // 每次将结果放到vv中，包括了空集
for(int i = index; i < nums.size(); ++i)
{
// used[i - 1]==false实际上只对同层树层有影响，对树枝是没有影响的，因为访问树枝的时候已经改成了true，而访问树层的时候一定是false
if(i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false)
continue;
v.push_back(nums[i]); // 处理
used[i] = true;
backtracking(nums, i + 1, used); // 递归
used[i] = false; // 回溯
v.pop_back();
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<bool> used(nums.size(), false);
sort(nums.begin(), nums.end()); // 记得先
backtracking(nums, 0, used);
return vv;
}
private:
vector<int> v;
vector<vector<int>> vv;
};