组合+并集问题汇总:
1、子集去重版本
2、组合非去重版本
3、组合去重版本
题目
注意:这里的nums数组里面的元素是各不相同的,所以不存在去重操作
方法一:动态规划
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();//结果集
res.add(new ArrayList<>());// 首先将空集加入解集中
int n = nums.length;
List<Integer> zres = null;
for(int i = 0 ; i < n ; i++){
int size = res.size(); // 当前子集数
for(int j = 0 ; j<size ;j++){
zres = new ArrayList<>(res.get(j));// 拷贝所有子集
zres.add(nums[i]);// 向拷贝的子集中加入当前数形成新的子集
res.add(zres);// 向lists中加入新子集
}
}
return res;
}
方法二:递归加回溯(关键----startIndex)
参考讲解视频:回溯算法解决子集问题,树上节点都是目标集和! | LeetCode:78.子集
根据nums[1,2,3] 可以画出树图,收获的结果集为所有节点,并且根据startIndex 每次只能取startIndex 后面的数,这样可以避免取到【1,2】 【2,1】这样的集合 这两个集合其实是同一个子集,所以每次递归都让startIndex +1 让递归后的只能取startIndex 后面的数
并且注意回溯(在递归后删除递归前加入的数)
文章来源:https://www.toymoban.com/news/detail-709109.html
文章来源地址https://www.toymoban.com/news/detail-709109.html
List<List<Integer>> res = new ArrayList<>();//结果集
public List<List<Integer>> subsets(int[] nums) {
List<Integer> zres = new ArrayList<>();
int startIndax = 0;//每一次取子结果的开始位置,第一次肯定从第一个位置开始
dfsback(nums,startIndax,zres);
return res;
}
//递归+回溯
public void dfsback(int[]nums,int startIndax, List<Integer> zres){
res.add(new ArrayList<>(zres));//收获结果
if(startIndax >= nums.length) return ;//这个条件有没有都没关系 因为如果startIndax >= nums.length 那么下面的for循环根本不会执行 自然会return掉
for(int i = startIndax ; i<nums.length ;i++){
zres.add(nums[i]);//收获子结果集
dfsback(nums,i + 1 ,zres);//往下递归
zres.remove(zres.size()-1);//回溯,还原状态
}
}
到了这里,关于【LeetCode-中等题】78. 子集的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!