78. 子集
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subsets-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路及方法
标准的回溯解法，说两点：
1.start表示数组元素要推进；
2.因为空数组也是子集，所以每一次递归都要添加trace，一直到trace.size() == nums.length。
class Solution {
List<List<Integer>> res = new LinkedList<>();
public List<List<Integer>> subsets(int[] nums) {
LinkedList<Integer> trace = new LinkedList<>();
int start = 0;
backTrace(nums, start, trace);
return res;
}
public void backTrace(int[] nums, int start, LinkedList<Integer> trace) {
res.add(new LinkedList<>(trace));
if (trace.size() == nums.length) {
return;
}
for (int i = start; i < nums.length; i++) {
// 做选择
trace.add(nums[i]);
// 进入下一层
backTrace(nums, i + 1, trace);
//回溯
trace.removeLast();
}
}
}
结果如下：
90. 子集 II
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subsets-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路及方法
跟上题类似，我的解法比较麻烦是因为去重的方法是先对数组进行排序，然后再去重添加。
class Solution {
List<List<Integer>> res = new LinkedList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
LinkedList<Integer> trace = new LinkedList<>();
int start = 0;
backTrace(nums, start, trace);
return res;
}
public void backTrace(int[] nums, int start, LinkedList<Integer> trace) {
List<Integer> tmp = new LinkedList<>(trace);
// 添加子集
if (!res.contains(tmp)) {
res.add(tmp);
}
if (trace.size() == nums.length) {
return;
}
for (int i = start; i < nums.length; i++) {
// 做选择
trace.add(nums[i]);
// 进入下一层
backTrace(nums, i + 1, trace);
//回溯
trace.removeLast();
}
}
}
结果如下：
