题目

思路

图中将used的变化⽤橘⻩⾊标注上，可以看出在candidates[i] == candidates[i - 1]相同的情况下：

• used[i - 1] == true，说明同⼀树⽀candidates[i - 1]使⽤过

• used[i - 1] == false，说明同⼀树层candidates[i - 1]使⽤过

  代码

  ```java class Solution {

  List< List > result = new ArrayList<>();

  LinkedList path = new LinkedList<>();

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    boolean[] used = new boolean[candidates.length];
    //剪枝排序
    Arrays.sort(candidates);
    backtracking(candidates,target,0,0,used);
    return result;
}
public void backtracking(int[] candidates, int target, int sum, int startIndex, boolean[] used) {
    if(sum > target) {
        return ;
    }
    if(sum == target) {
        result.add(new ArrayList(path) );
        return ;
    }
    for(int i = startIndex ; i < candidates.length && sum + candidates[i] <= target; i++ ) {
        if(i > 0 && candidates[i] == candidates[i-1] && used[i - 1] == false ) {
            continue;
        }
        if(sum == target) {
            result.add(path);
            return ;
        }
        used[i] = true;
        sum += candidates[i];
        path.add(candidates[i]);
        backtracking(candidates,target,sum,i+1,used);
        path.removeLast();
        used[i] = false;
        sum -= candidates[i];
    }
}

} ```