78. 子集
給你一個整數(shù)數(shù)組 nums 仅政，其中可能包含重復元素，請你返回該數(shù)組所有可能的子集（冪集）盆驹。
解集 不能 包含重復的子集圆丹。返回的解集中，子集可以按 任意順序 排列躯喇。
示例 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
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有辫封。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
解題思路及方法
標準的回溯解法倦微，說兩點：
1.start表示數(shù)組元素要推進妻味；
2.因為空數(shù)組也是子集，所以每一次遞歸都要添加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();
}
}
}
結(jié)果如下：
90. 子集 II
給你一個整數(shù)數(shù)組 nums ，其中可能包含重復元素劣欢，請你返回該數(shù)組所有可能的子集（冪集）棕诵。
解集 不能 包含重復的子集。返回的解集中凿将，子集可以按 任意順序 排列校套。
示例 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
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)牧抵，非商業(yè)轉(zhuǎn)載請注明出處笛匙。
解題思路及方法
跟上題類似，我的解法比較麻煩是因為去重的方法是先對數(shù)組進行排序犀变，然后再去重添加妹孙。
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();
}
}
}
結(jié)果如下：
