目录
题目
思路
代码
题目
给定一个候选人编号的集合 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] ]
思路
本题的特殊之处：
candidate中的元素可以重复，但是结果中的组合不能重复（集合（数组candidates）有重复元素，但还不能有重复的组合。）
这道题的去重需要从两个维度上思考：
- 树层上的去重
- 树枝上的去重
这道题我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。
首先对数组排序，使得相同的元可以相邻
对于回溯的参数传递：因为有相同元素，所以需要定义一个used数组，来标记，这个数字是否使用过。
对于单层搜索的逻辑：
要去重的是“同一树层上的使用过”，如何判断同一树层上元素（相同的元素）是否使用过了呢。
如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false，就说明：前一个树枝，使用了candidates[i - 1]，也就是说同一树层使用过candidates[i - 1]。
此时for循环里就应该做continue的操作。
可以看出在candidates[i] == candidates[i - 1]相同的情况下：
- used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
- used[i - 1] == false，说明同一树层candidates[i - 1]使用过
代码
class Solution {List<List<Integer>> result=new ArrayList<>();
//最后的结果集LinkedList<Integer> path=new LinkedList<>();
//收集叶子节点用的集合int sum=0;//记录叶子节点的和boolean [] used;//用来标记是否使用过集合中 的数字public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);//排序，将重复的数字都放到一起used = new boolean[candidates.length];// 加标志数组，用来辅助判断同层节点是否已经遍历Arrays.fill(used,false);//初始状态是都未使用，标成falsebackTracking(candidates,target,0);return result;}public void backTracking(int[] candidates, int target,int startIndex){if(sum==target){//叶子节点符合条件result.add(new ArrayList(path));}for(int i=startIndex;i<candidates.length;i++){if(i>0&&candidates[i]==candidates[i-1]&&!used[i-1]){//去重continue;}if(candidates[i]+sum>target) break;used[i]=true;sum+=candidates[i];path.add(candidates[i]);backTracking(candidates,target,i+1);sum-=candidates[i];//回溯，恢复初始状态used[i]=false;path.removeLast();}}
}
