【LeetCode-中等题】78. 子集

题目

注意：这里的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 后面的数

并且注意回溯（在递归后删除递归前加入的数）

    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);//回溯，还原状态}}