78、子集
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
题解
1、递归回溯
深度优先搜素
class Solution {
List<List<Integer>> res = new ArrayList<List<Integer>>();
public List<List<Integer>> subsets(int[] nums) {
//2^nums.length 个集合
subsets(nums,0,new LinkedList<Integer>());
return res;
}
private void subsets(int[] nums, int index,LinkedList<Integer> temp){
res.add(new LinkedList<Integer>(temp));
for (int i = index; i < nums.length;++i) {
temp.add(nums[i]);
subsets(nums,i+1,temp);
temp.removeLast();
}
}
}
2、迭代法
class Solution {
public List<List<Integer>> subsets(int[] nums) {
// 结果
List<List<Integer>> list = new ArrayList<>();
// 特殊case
if(nums.length == 0) return list;case
// 空集也是子集
list.add(new ArrayList<>());
for(int i = 0;i < nums.length;i++){
int size = list.size();
List<Integer> list2 = null;
// 遍历已有的结果
for(int j = 0;j < size;j++){
list2 = new ArrayList<>();
// 复制一个已有的子集
list2.addAll(list.get(j));
// 加入新的元素成为新的子集
list2.add(nums[i]);
// 加入新的子集
list.add(list2);
}
}
return list;
}
}
90 子集II
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
题解
1、递归回溯——深度优先搜索
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
// 回溯法
List<List<Integer>> res = new ArrayList<List<Integer>>();
// 排序方便剪枝
Arrays.sort(nums);
subsetsWithDupCore(nums,0,new ArrayList<>(),res);
return res;
}
private void subsetsWithDupCore(int[] nums,int index,List<Integer> temp,List<List<Integer>> res) {
// 新增一个结果
res.add(new ArrayList<Integer>(temp));
// 遍历所有剩余结点
for (int i = index;i < nums.length;i++) {
// 剪枝判断
if (i > index && nums[i] == nums[i-1]) {
continue;
}
temp.add(nums[i]);
// 递归, 索引用i
subsetsWithDupCore(nums,i+1,temp,res);
// 移除元素进行回溯
temp.remove(temp.size() - 1);
}
}
}
2、迭代法
利用旧的解去生成新的解，去除重复的情况。
- 分析迭代过程去除重复解
我们看到第 4 行黑色的部分，重复了，是怎么造成的呢？
第 4 行新添加的 2 要加到第 3 行的所有解中，而第 3 行的一部分解是旧解，一部分是新解。可以看到，我们黑色部分是由第 3 行的旧解产生的，橙色部分是由新解产生的。
而第 1 行到第 2 行，已经在旧解中加入了 2 产生了第 2 行的橙色部分，所以这里如果再在旧解中加 2 产生黑色部分就造成了重复。
所以当有重复数字的时候，我们只考虑上一步的新解，算法中用一个指针保存每一步的新解开始的位置即可。
作者：windliang
链接：https://leetcode-cn.com/problems/subsets-ii/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-19/
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> res = new ArratList<List<Integer>>();
Arrays.sort(nums);
int index = 1;// 保存新解的位置
for (int i = 0;i < nums.length;i++) {
List<List<integer>> res_temp = new ArrayList<List<Integer>>();
for (int j = 0;j < res.size();j++) {
// remove dup temp cases
// i > 0 && nums[i] == nums[i-1] 表示有重复数字
// j < start 表示要当前位置不是上一次新解开始的位置
if (i > 0 && nums[i] == nums[i-1] && j < start) {
continue;
}
List<Integer> temp = new ArrayList<>(res.get(j));
temp.add(nums[i]);
res_temp.add(temp);
}
// 更新新解的开始位置
start = res.size();
res.addAll(res_temp);
}
return res;
}
- 统计当前的重复元素个数来去除重复解
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> empty = new ArrayList<>();
res.add(empty);
Arrays.sort(nums);
for (int i = 0;i < nums.length;i++) {
// 统计数值为nums[i]重复元素个数
int dupCount= 0;
while((i+1) < nums.length && nums[i+1] == nums[i]) {
dupCount++;
i++;// 下标后移，跳过重复元素
}
int preNum = res.size();
for（int j = 0;j < preNum;j++) {
List<Integer> temp = new ArrayList<>(res.get(j));
// 逐个添加重复元素
for (int k = 0;k < dupCount;k++) {
temp.add(nums[i]);
res.add(temp);
}
}
}
return res;
}
3、利用位操作
数组元素过多时，会超时。
class Solution{
public List<List<Integer>> subsetsWithDup(int[] num) {
Arrays.sort(num);
List<List<Integer>> lists = new ArrayList<>();
int subsetNum = 1<<num.length;
// 遍历所有的位
for(int i = 0;i < subsetNum;i++){
List<Integer> list = new ArrayList<>();
boolean illegal = false;// 非法位判断
// 遍历数组
for(int j = 0;j < num.length;j++){
//当前位是 1
if((i >> j & 1) == 1){
//当前是重复数字，并且前一位是 0，跳过这种情况
if(j > 0 && num[j] == num[j-1] && (i >> (j - 1) & 1) == 0){
illegal = true;
break;
}else{
list.add(num[j]);
}
}
}
if(!illegal){
lists.add(list);
}
}
return lists;
}
}
// 作者：windliang
// 链接：https://leetcode-cn.com/problems/subsets-ii/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-19/
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
