给你一个整数数组 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
- 首先明白什么时候会产生重复的情况，例如 [1, 2, 2] 。对于每一层搜索有两个选择，选择该数与不选择该数，当选了1后，对于第一个2来说，分为选择与不选择，产生1 2 与1 _ ,然后1 _ 遇上第二个2也会有选择与不选择的情况产生1 _ _ 和1 _ 2，这时候便产生重复。因此当上一步操作没有选择数，并且当前数与上一个数相同时，不进行当前数的选择。
class Solution {
List<List<Integer>> ans = new ArrayList<>();
LinkedList<Integer> rec = new LinkedList<>();
int n;
public List<List<Integer>> subsetsWithDup(int[] nums) {
n = nums.length;
Arrays.sort(nums);
dfs(0, nums, true); //从第一个位置开始搜索
return ans;
}
void dfs(int x, int[] nums, boolean sel) {
if (x == n) {
ans.add(new ArrayList<Integer>(rec));
return;
}
//不考虑放入x位置的数
dfs(x + 1, nums, false);
//考虑当前位置
if (!sel && x > 0 && nums[x] == nums[x - 1]) return;
rec.add(nums[x]);
dfs(x + 1, nums, true);
rec.removeLast();
}
}