题目

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

提示:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

题解

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    Set<List<Integer>> result = new HashSet<>(6);
    Arrays.sort(candidates);

    TrConsumer<Integer, Integer, List<Integer>> consumer = new TrConsumer<Integer, Integer, List<Integer>>() {
        @Override
        public void accept(Integer index, Integer sum, List<Integer> list) {
            int left = target - sum;
            if (left == 0) {
                // 排序去重
                List<Integer> temp = new ArrayList<>(list);
                Collections.sort(temp);
                result.add(temp);
            } else if (left > 0) {
                // 还可以加数字
                // 只能加小于等于剩余值的数字
                for (int i = index; i < candidates.length && candidates[i] <= left; i++) {
                    int current = candidates[i];
                    list.add(current);
                    // 从下一个位置继续计算
                    this.accept(i + 1, sum + current, list);
                    // 回溯
                    list.remove(list.size() - 1);
                }
            }
            // 剩余数字小于零 不满足条件
        }
    };

    consumer.accept(0, 0, new ArrayList<>());

    return new ArrayList<>(result);
}

private interface TrConsumer<T, U, P> {
    void accept(T t, U u, P p);
}