40-组合总和II

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    backtrace(candidates, target, new ArrayList<>(), 0, 0);
    return new ArrayList<>(res);
}

private Set<List<Integer>> res = new HashSet<>();
public void backtrace(int[] candidates, int target, List<Integer> path, int index, int sum){
    //结束条件：路径中的和等于target
    if (sum == target){
        ArrayList<Integer> re = new ArrayList<>(path);
        Collections.sort(re);
        res.add(re);
        return ;
    }
    for (int i = index; i < candidates.length; i++) {
        //剪枝
        if (sum > target) return ;
        //做选择
        sum += candidates[i];
        path.add(candidates[i]);
        //递归
        backtrace(candidates, target, path, i + 1, sum);
        //撤销
        sum -= candidates[i];
        path.remove(path.size() - 1);
    }
}

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    Arrays.sort(candidates);	//一次性排序
    backtrace2(candidates, target, new ArrayList<>(), 0, 0);
    return new ArrayList<>(res);
}

private Set<List<Integer>> res = new HashSet<>();

public void backtrace2(int[] candidates, int target, List<Integer> path, int index, int sum){
    //结束条件：路径中的和等于target
    if (sum == target){
        res.add(new ArrayList<>(path));
        return ;
    }
    for (int i = index; i < candidates.length; i++) {
        //剪枝
        if (sum > target) return ;
        //做选择
        if(i > index && candidates[i] == candidates[i-1]) continue; //去重，第二次加入和前一次一样，则continue
        sum += candidates[i];
        path.add(candidates[i]);
        //递归
        backtrace2(candidates, target, path, i + 1, sum);
        //撤销
        sum -= candidates[i];
        path.remove(path.size() - 1);
    }
}