40. 组合总和 II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]

思路

此题与39题区别：候选数字有重复的，但每个数字只能使用一次
1 仍然需要排序，便于后续剪枝
2 递归出口
符合结果：与39题一致。子集每加入一个数字，target减去相应的数字，当target为0时，表示改子集满足条件，是一个结果（反向思维，相加也行，比较sum和target）
剪枝条件：
1 与39题一致。target-候选数字小于0时，后面比它更大的就不用计算了，例如图中的2-2-2-2与2-2-2-3，直接break
2 当当前候选数字与上一个候选数字一致时，所有情况也已经计算过，跳过该数字continue

代码

class Solution {

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates);
        func(new LinkedList<>(), candidates, target, 0, candidates.length, res);
        return res;
    }

    private void func(Deque<Integer> sub, int[] candidates, int target, int i, int length,
        List<List<Integer>> res) {
        if (target == 0) {
            res.add(new ArrayList<>(sub));
            return;
        }
        for (int index = i; index < length; index++) {
            if (target - candidates[i] < 0){
                break;
            }
            if (index > i && candidates[index] == candidates[index-1]){
                continue;
            }
            sub.addLast(candidates[index]);
            func(sub, candidates, target - candidates[index], index + 1, length, res);
            sub.removeLast();
        }
    }
}