90. 子集 II
给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。
思路
一看到子集,立马就能想到回溯
因为包含有重复元素,所以去重是一个问题。
对于重复元素,该元素的单个集合会导致重复。
一开始想着用set去重,但是回溯肯定要在递归过程中剪枝才对。
看了题解,这里的剪枝真的神。
if(i > index && nums[i] == nums[i - 1]) {
continue;
}
完整代码
List<List<Integer>> ans = new ArrayList<>();
List<Integer> list = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
backTrack(nums, 0);
return ans;
}
public void backTrack(int[] nums, int index) {
ans.add(new ArrayList<>(list));
for(int i = index; i < nums.length; i++) {
if(i > index && nums[i] == nums[i - 1]) {
continue;
}
list.add(nums[i]);
backTrack(nums, i + 1);
list.remove(list.size() - 1);
}
}
39. 组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
思路
一开始的思路是设置一个temp=0,每次添加的时候求得temp的值,当temp== target的时候存储。
这样做的时候十分容易重复。因为
List<List<Integer>> ans = new ArrayList<>();
List<Integer> list = new ArrayList<>();
int temp = 0;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
if(candidates.length == 0){
return ans;
}
backTrack(candidates, 0, target);
return ans;
}
public void backTrack(int[] nums, int index,int target) {
if(target == 0){
ans.add(new ArrayList<>(list));
return;
}
for(int i = index; i < nums.length; i++){
if(nums[i] <= target){
list.add(nums[i]);
backTrack(nums, i, target - nums[i]);
list.remove(list.size() - 1);
}
}
}