LeetCode40：组合总和II

原题地址：. - 力扣（LeetCode）

题目描述

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

解题思路

从给定的候选数字数组 candidates 中找出所有和为 target 的组合，但与之前的问题不同，这个变种允许使用候选数字数组中的数字多次，且组合中的数字不一定要连续。代码中使用了深度优先搜索（DFS）算法来解决这个问题，并进行了一些优化：

1. 预处理：首先对候选数字数组进行排序，并使用 freq 数组来存储每个不同数字的频率。
2. DFS：深度优先搜索函数 dfs 用于递归地构建所有可能的组合。

在 dfs 方法中，我们有两个选择：

• 跳过当前数字：直接递归调用 dfs 方法，尝试下一个数字。
• 选择当前数字：如果当前目标 rest 大于等于候选数字，则将该数字添加到 sequence 列表中，并递归调用 dfs 方法，目标减去该数字的倍数，直到超过剩余目标或超过当前数字的频率。

代码实现

class Solution {// 存储每个数字的频率List<int[]> freq = new ArrayList<>();// 存储所有有效的组合List<List<Integer>> ans = new ArrayList<>();// 存储当前的组合List<Integer> sequence = new ArrayList<>();public List<List<Integer>> combinationSum2(int[] candidates, int target) {// 对候选数字数组进行排序Arrays.sort(candidates);// 计算每个数字的频率for (int num : candidates) {int size = freq.size();// 如果当前数字与前一个数字不同，或者freq为空，则添加新的频率记录if (freq.isEmpty() || num != freq.get(size - 1)[0]) {freq.add(new int[]{num, 1});} else {// 否则，增加相同数字的频率++freq.get(size - 1)[1];}}// 开始深度优先搜索dfs(0, target);// 返回所有有效的组合return ans;}public void dfs(int pos, int rest) {// 如果剩余目标为0，说明找到了一个有效的组合，添加到结果列表中if (rest == 0) {ans.add(new ArrayList<>(sequence));return;}// 如果位置超出freq数组范围，或者剩余目标小于当前数字，返回if (pos == freq.size() || rest < freq.get(pos)[0]) {return;}// 先不选择当前数字，递归搜索下一个数字dfs(pos + 1, rest);// 选择当前数字，最多选择至多等于剩余目标或当前数字频率的最小值int most = Math.min(rest / freq.get(pos)[0], freq.get(pos)[1]);for (int i = 1; i <= most; ++i) {// 将当前数字添加到组合中sequence.add(freq.get(pos)[0]);// 递归搜索下一个数字，目标减去当前数字dfs(pos + 1, rest - i * freq.get(pos)[0]);}// 回溯，移除添加的当前数字for (int i = 1; i <= most; ++i) {sequence.remove(sequence.size() - 1);}}
}

复杂度分析

• 时间复杂度：最坏情况下，DFS 会尝试所有可能的组合，但由于进行了剪枝（即跳过大于剩余目标的数字），实际的时间复杂度通常要好于 O(2^n)，但最坏情况下仍然是指数级别的。

• 空间复杂度：空间复杂度主要取决于递归栈的深度和 sequence 列表的大小。最坏情况下，递归栈的深度和 sequence 的大小都不超过 target，所以空间复杂度为 O(target)。