Leetcode-day23-回溯-子集问题

​​​​​​​​​​​​​​78. 子集

今天的两个题都是不需要结束return条件的，因为要找所有节点的元素，for循环遍历完之后自然就结束了

这个问题就简单多了，以前找的是叶子节点，现在是要把所有节点都找出来。

class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>(); public List<List<Integer>> subsets(int[] nums) {backTrack(nums,0);return res;}public void backTrack(int[] nums,int startIndex){res.add(new ArrayList(path));for(int i=startIndex;i<nums.length;i++){path.add(nums[i]);backTrack(nums,i+1);path.remove(path.size()-1);}}
}

90. 子集 II

这个题也比较简单，有了前面的基础之后，其实就是多了一个去重操作。

首先要区分好树层和树枝，树枝上也就是纵向是可以重复取的，但是树层上是不能重复取的

首先要对数组进行排序，方便左判断，然后我们可以做一个flag数组来记录每个元素是否被取到了，如图所示如果是纵向，树枝被取到了，flag[i-1]是true，而如果是横向的树层则是false，因为已经被回溯了，这时候直接continue就可以了。

class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>(); public List<List<Integer>> subsetsWithDup(int[] nums) {Arrays.sort(nums);boolean[] flag = new boolean[nums.length]; backTrack(nums,0,flag);return res;}public void backTrack(int[] nums,int startIndex,boolean[] flag){res.add(new ArrayList(path));for(int i=startIndex;i<nums.length;i++){if(i>0&&nums[i]==nums[i-1]&&flag[i-1]==false){continue;}flag[i]=true;path.add(nums[i]);backTrack(nums,i+1,flag);flag[i]=false;path.remove(path.size()-1);}}
}