给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subsets-ii
解题思路
采用深度优先搜索
dfs(int[] nums, int start, Deque<Integer> path, List<List<Integer>> result)
参数依次是数组，起始拼接位置，搜索过程中的路径，结果集
因为不能出现重复元素，比如[1, 2, 2]这个集合，会出现两个[1, 2]
这时要考虑"剪枝"，剪枝的前提是将数组排序
然后考虑剪枝的条件"同一层不能用相同数字"
比如[1, 2, 2]深度优先遍历时
image.png
在代码中如何呈现？
在关键方法 dfs() 中，for 循环代表了同一层，而递归代表了不同层
所以在 for 循环中要判断索引 i 是否为起始索引，不是起始索引且和前一个元素相同则剪枝
代码
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> result = new LinkedList<>();
if (nums == null || nums.length == 0) {
return result;
}
result.add(new ArrayList<>()); // 空集
Arrays.sort(nums);
Deque<Integer> path = new LinkedList<>();
dfs(nums, 0, path, result);
return result;
}
private void dfs(int[] nums, int start, Deque<Integer> path, List<List<Integer>> result) {
for (int i = start; i < nums.length; i++) {
if (i == start || nums[i] != nums[i - 1]) {
path.addLast(nums[i]);
result.add(new ArrayList<>(path));
dfs(nums, i + 1, path, result);
path.removeLast();
}
}
}
}
