北京网站建设手机app电子商务,建筑公司信用分查询官网,电子商务平台经营者,汽车类网站建设预算文章目录 组合并集问题汇总#xff1a;题目方法一#xff1a;动态规划方法二#xff1a;递归加回溯(关键----startIndex) 组合并集问题汇总#xff1a;
1、子集去重版本 2、组合非去重版本 3、组合去重版本
题目 注意#xff1a;这里的nums数组里面的元素是各不相同的并集问题汇总题目方法一动态规划方法二递归加回溯(关键----startIndex) 组合并集问题汇总
1、子集去重版本 2、组合非去重版本 3、组合去重版本
题目 注意这里的nums数组里面的元素是各不相同的所以不存在去重操作
方法一动态规划 public ListListInteger subsets(int[] nums) {ListListInteger res new ArrayList();//结果集res.add(new ArrayList());// 首先将空集加入解集中int n nums.length;ListInteger zres null;for(int i 0 ; i n ; i){int size res.size(); // 当前子集数for(int j 0 ; jsize ;j){zres new ArrayList(res.get(j));// 拷贝所有子集zres.add(nums[i]);// 向拷贝的子集中加入当前数形成新的子集res.add(zres);// 向lists中加入新子集}}return res;}方法二递归加回溯(关键----startIndex)
参考讲解视频:回溯算法解决子集问题树上节点都是目标集和 | LeetCode78.子集
根据nums[1,2,3] 可以画出树图收获的结果集为所有节点并且根据startIndex 每次只能取startIndex 后面的数这样可以避免取到【1,2】 【2,1】这样的集合 这两个集合其实是同一个子集所以每次递归都让startIndex 1 让递归后的只能取startIndex 后面的数
并且注意回溯在递归后删除递归前加入的数 ListListInteger res new ArrayList();//结果集public ListListInteger subsets(int[] nums) {ListInteger zres new ArrayList();int startIndax 0;//每一次取子结果的开始位置第一次肯定从第一个位置开始dfsback(nums,startIndax,zres);return res;}//递归回溯public void dfsback(int[]nums,int startIndax, ListInteger zres){res.add(new ArrayList(zres));//收获结果if(startIndax nums.length) return ;//这个条件有没有都没关系 因为如果startIndax nums.length 那么下面的for循环根本不会执行 自然会return掉for(int i startIndax ; inums.length ;i){zres.add(nums[i]);//收获子结果集dfsback(nums,i 1 ,zres);//往下递归zres.remove(zres.size()-1);//回溯还原状态}}
