- 组合总和 II
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]
思考
这个比较特殊
- 每个数使用一次
- 有相同的数
- 结果不能重复(因为有相同的数，所以相同的数不用重复使用)
- 解决办法
- 办法一：事先对数组进行排序，如果当前节点的值等于上一个节点的值，continue，for横向循环下一个节点。
- 方法二: 对该数组设置状态变量used数组，这样可以判断该数值是否被使用
- 解决办法
对于每个数只能使用一次，
- 我们对横向for循环设置起始坐标startIndex,随着递归，横向for循环起始位置加一。
对于有相同的数
- 事先对数组进行排序，对于同层相邻的数值相同会出现重复(如下图)。我们只选取该层的相同的数值的第一个即可，其他与同一层前一个数值相同的跳过即可。
- 即满足
i>0&&candidates[i-1] == candidates[i]&&i!=startIndex i>0candidates[i-1] == candidates[i]同层前面的数与该数相同i!=startIndex该层的起始节点不跳过
同时进行两个剪支操作
向下剪支 该节点的下方都不符合条件 ，此时这个当前sum是上一层的结果，其实就是去遍历上一层的下一个节点
if(sum>target)return;
向右剪枝 该节点的不符合条件，由于是有序数组，其节点右方更不会符合条件
if(candidates[i] + sum > target) return;
回溯中for循环中使用break和continue的理解
break 回到上一层
continue 在当前层遍历
class Solution {
int sum = 0;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> lists=new ArrayList<>();
List<Integer> list=new ArrayList<>();
int startIndex=0;
Arrays.sort(candidates);
backTracking(lists,list,candidates,target,startIndex);
return lists;
}
private void backTracking(List<List<Integer>> lists, List<Integer> list, int[] candidates, int target,int startIndex) {
if(sum>target)return;
if(sum == target){
lists.add(new ArrayList<>(list));
return;
}
for (int i = startIndex; i < candidates.length; i++) {
if(candidates[i] + sum > target) return;
if(i>0&&candidates[i-1] == candidates[i]&&i!=startIndex){
continue;
}
list.add(candidates[i]);
sum = sum + candidates[i];
backTracking(lists,list,candidates,target,i+1);
list.remove(list.size()-1);
sum = sum - candidates[i];
}
}
}
