LeetCode 40.组合总和II

1.题目：

给定一个候选人编号的集合 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] ]

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/combination-sum-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2.代码：

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;//定义一个boolean类型的数组，来判断这个数组的元素是否遍历了
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        used = new boolean[candidates.length];
         //Arrays.fill(used, false);//不赋值的话，初始值也是false
        if(candidates.length==0) return result;
        Arrays.sort(candidates);//先把数组进行排序，方便去重
        backtracking(candidates,target,0,0);
        return result;

    }
    public void backtracking(int[] candidates,int target,int sum,int startIndex){
     //   if(sum>startIndex) return;
        if(sum==target) {//满足条件就放到结果集当中
            result.add(new ArrayList<>(path));
            return;
        }
        for(int i=startIndex; i<candidates.length; i++){
            if((sum+candidates[i])>target) break;//剪枝，当和大于target之后就直接跳出循环
            //去重的操作，注意要有i>0的初始条件，然后就是后一个元素跟前一个元素相同时，并且保证这一层循环是树层，而不是树枝，所以就是false
            if(i>0 && candidates[i]==candidates[i-1] && used[i-1]==false) continue;//重复的就跳过这次循环
            path.add(candidates[i]);//添加到一个暂时的集合里面去
            sum+=candidates[i];//累加
            used[i]=true;//更新used的值，声明这个元素已经用过了
            backtracking(candidates,target,sum,i+1);//递归
            path.remove(path.size()-1);//集合回溯
            sum-=candidates[i];//sum回溯（回退）
            used[i]=false;//数组回溯
            
        }
    }
}