78.子集90.子集2

78.子集

思路

又回到了组合的模板中来，这道题相比于前面的题省去了递归终止条件。大差不差。

代码

class Solution {List<List<Integer>> result =new ArrayList<>();LinkedList<Integer> list=new LinkedList<>();public List<List<Integer>> subsets(int[] nums) {backTracking(nums,0);return result;}public void backTracking(int[] nums,int startIndex){result.add(new ArrayList<>(list));for (int i=startIndex;i<nums.length;i++){list.add(nums[i]);backTracking(nums,i+1);list.removeLast();}}
}

90.子集2

思路

增加了个对重复的判断操作，好像之前组合也做过类似的，数组排序+去重。

去重就简单将前后两个数字进行比较，若相等则跳过，唯一需要注意的地方就是每层（每个位置）第一次循环的数字不进行去重。

代码

class Solution {List<List<Integer>> result =new ArrayList<>();LinkedList<Integer> list=new LinkedList<>();public List<List<Integer>> subsetsWithDup(int[] nums) {Arrays.sort(nums);backTracking(nums,0);return result;}public void backTracking(int[] nums,int startIndex){result.add(new ArrayList<>(list));for (int i=startIndex;i<nums.length;i++){if (i>startIndex && nums[i]==nums[i-1]) continue; //去重list.add(nums[i]);backTracking(nums,i+1);list.removeLast();}}
}