给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]示例 2：
输入：nums = [0]
输出：[[],[0]]在一个数组中存在重复元素，找到所有可能的子集（幂集）。
这个问题与 LeetCode-78. 子集 类似，不同之处在于 本题中的数组存在重复元素。
第二类：对某种数结构和算法的使用
使用的算法：在给定的元素集合中，找到元素满足条件的组合，使用“回溯算法“
数据结构：回溯算法需要构建空间状态树，使用树结构
确定“回溯算法”中的必需要素，然后用代码实现。
方法
（1）选择列表
数组中的所有元素；
数组中存在重复的元素，却要求子集中不能存在重复的元素，可以先对数组排序。
（2）路径
每个元素在一个子集中只能使用一次，所以要记录已经选择的元素下标；
同一个递归路径下，不同子集之间有着相同的前缀，因此在方法
（3）结束条件
当 $idx \ge nums.length $ 时，表示数组中所有元素都已经遍历过，此时可以结束方法。
（4）选择
什么条件下才把当前遍历的元素添加进路径中？
根据要求，对排序后的数组进行遍历时，如果
从下面的“空间状态树”可以看出，此时有两种情况：
- 在同一层递归中，$nums[idx-1]$ 不在路径中，忽略$nums[idx]$
- 在不同层递归中，$nums[idx-1]$ 在路径中，选择$nums[idx]$
"空间状态树"如下图所示：
public class Solution {
public static void main(String[] args) {
int[] nums = new int[]{4, 4, 4, 1, 4};
System.out.println("'========='" + new Solution().subsetsWithDup(nums));
}
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
backtrack(res, new ArrayList<>(nums.length), nums, new boolean[nums.length], 0);
return res;
}
public void backtrack(List<List<Integer>> res, List<Integer> path, int[] nums, boolean[] visited, int idx) {
res.add(new ArrayList<>(path));
if (idx >= nums.length) {
return;
}
for (int i = idx; i < nums.length; i++) {
if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
continue;
}
path.add(nums[i]);
visited[i] = true;
backtrack(res, path, nums, visited, i + 1);
path.remove(path.size() - 1);
visited[i] = false;
}
}
}1、在有重复元素的数组中，生成不存在重复元素的组合，同样可以先排序后选择；
2、同一条递归路径下的子集，有着相同的前缀，可以在进入递归时，先把路径添加到结果中。