LeetCode40. 组合总和 II（Java版）

1984. 学生分数的最小差值（简单）

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

思路

题目拿来一看感觉怎么样做，时间复杂度都很高。于是想着先使用递归 + 回溯 + 剪枝的方法做完提交一下试试。

先将数组排序，针对每个数组元素都可以选择选或者不选（回溯体现在这里），在某次递归前，如果刚好已选择的数组元素之和 等于 target，则保存当前序列。这样搞完，发现有重复的序列保存到了结果中。

这怎么搞撒，将相同的数放在一起进行处理；即如果数x 出现了 y 次，那么在递归时一次性地处理它们，即分别调用选择0,1,⋯,y 次 x 的递归函数（首先要维护每个数出现的次数）。dfs递归如下：dfs(pos+1,rest−y×freq[pos][0])。

剪枝体现在如果当前位置的数据已经大于rest了，后面的数据就不要遍历了（排序后的数组）。

代码

可以将代码中的全局变量修改为方法的入参。

class Solution {

    List<int[]> frequency = new ArrayList<>();
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();

    /**
     * 方法：递归遍历 + 回溯
     * 时间复杂度：O(2^n * n)，递归时每个位置可选可不选，所以有2^n种情况；针对每个组合有O(n)复杂度将其放入答案中
     * 空间复杂度：O(n)，递归中存放的frequency、temp、栈空间都是O(n)
     */
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if (candidates == null || candidates.length < 1) {
            return res;
        }
        Arrays.sort(candidates);
        for (int candidate : candidates) {
            int size = frequency.size();
            if (frequency.isEmpty() || candidate != frequency.get(size - 1)[0]) {
                frequency.add(new int[]{candidate, 1});
            } else {
                ++frequency.get(size - 1)[1];
            }
        }

        dfs(0, target);
        return res;
    }

    private void dfs(int pos, int rest) {
        // 满足条件
        if (rest == 0) {
            res.add(new ArrayList<>(temp));
            return;
        }
        if (pos == frequency.size() || frequency.get(pos)[0] > rest) {
            return;
        }

        // 递归
        dfs(pos + 1, rest);

        int count = frequency.get(pos)[1];
        int candidate = frequency.get(pos)[0];
        // 最多 需要/可以 使用当前元素的个数
        int most = Math.min(count, rest / candidate);
        // 选
        for (int i = 1; i <= most; i++) {
            temp.add(frequency.get(pos)[0]);
            dfs(pos + 1, rest - i * candidate);
        }

        // 不选
        for (int i = 1; i <= most; i++) {
            temp.remove(temp.size() - 1);
        }
    }
}