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();
}
}
}