040.组合总和 II
作者：沉默王二
发布时间：2024-08-04T19:24:57.139+0800
二哥说，今天去帮父亲干了半天的活，一身尘埃，但是感觉很充实，累但知道了生活的不易，更需要去珍惜现在拥有的一切，所以马不停蹄地继续刷题，今天的题目是组合总和 II，这道题目是一道中等难度的题目，但是，只要我们细心分析，就能迎刃而解。
题意
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
难度
中等
示例
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]
### 分析 1
很显然，这道题和 039.组合总和 是姊妹篇。不过，这道题要求同一个数字不能被重复选择，但是candidates中可能会存在有重复的数字。
同样我们也可以使用暴力，枚举所有的可能性，然后判断是否符合条件，如果符合条件就加入到答案中。
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
class Solution04001 {
public List<List
List<List
Arrays.sort(candidates); // 排序以便于后续处理
generateAllCombinations(candidates, target, new ArrayList<>(), result, 0);
return result;
}
private void generateAllCombinations(int[] candidates, int target, List<Integer> combination, List<List<Integer>> result, int start) {
int sum = combination.stream().mapToInt(Integer::intValue).sum();
if (sum > target) {
return;
}
if (sum == target) {
if (!result.contains(combination)) {
result.add(new ArrayList<>(combination)); // 创建组合的副本并添加到结果列表
}
return;
}
for (int i = start; i < candidates.length; i++) {
combination.add(candidates[i]);
generateAllCombinations(candidates, target, combination, result, i + 1); // 每个数字只能使用一次，所以递归从 i+1 开始
combination.remove(combination.size() - 1); // 回溯，撤销最后的选择
}
}
public static void main(String[] args) {
Solution04001 solution = new Solution04001();
int[] candidates = {10, 1, 2, 7, 6, 1, 5};
int target = 8;
List<List<Integer>> result = solution.combinationSum2(candidates, target);
System.out.println("所有组合: " + result);
}
}
代码很好理解：
计算当前组合的和 sum。
如果 sum 大于 target，直接返回，进行剪枝操作。
如果 sum 等于 target，检查结果列表中是否已经包含该组合，若不包含则添加该组合。
循环遍历从 start 到 candidates.length 的每一个元素：
将当前元素 candidates[i] 加入组合列表 combination。
递归调用 generateAllCombinations，继续生成可能的组合。
回溯，撤销当前选择，继续尝试下一个元素。
直接运行 main 方法也是可以得出结果的。
但是很遗憾，放在 LeetCode 上跑的时候，会发现超时了。
问题就在于，重复计算太多，和 039.组合总和 一样，我们需要优化。
分析 2
优化的思路和 039.组合总和 是一样的，我们可以先对数组进行排序，然后在递归的时候：
如果当前数字和上一个数字相同，我们直接跳过。
如果当前候选数字大于剩余的目标值，我们直接返回，然后进行剪枝操作。比如说 [1, 1, 2, 5, 6, 7]，目标值是 8，如果当前数字是 5，那么剩余的目标值是 4，而 5 已经大于 4 了，所以直接返回。然后把 2 剪枝掉，因为 1+1+2+后面任何一个数都不满足要求了。
好，我们来看题解：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
class Solution04002 {
private List<List
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates); // 排序以便于跳过重复元素
backtrack(candidates, target, 0, new ArrayList<>());
return result;
}
private void backtrack(int[] candidates, int target, int start, List<Integer> combination) {
if (target == 0) {
result.add(new ArrayList<>(combination));
return;
}
for (int i = start; i < candidates.length; i++) {
// 跳过同一层中重复的元素
if (i > start && candidates[i] == candidates[i - 1]) {
continue;
}
// 剪枝：当前候选数大于剩余目标值，直接返回
if (candidates[i] > target) {
break;
}
combination.add(candidates[i]);
// 递归调用时，下一次递归的起点要从当前元素的下一个元素开始
backtrack(candidates, target - candidates[i], i + 1, combination);
combination.remove(combination.size() - 1); // 回溯，撤销最后的选择
}
}
public static void main(String[] args) {
Solution04002 solution = new Solution04002();
int[] candidates = {10, 1, 2, 7, 6, 1, 5};
int target = 8;
List<List<Integer>> result = solution.combinationSum2(candidates, target);
System.out.println("所有组合: " + result);
}
}
基本情况：如果 target == 0，说明找到了一个符合条件的组合，将其加入结果列表 result。
循环遍历从 start 到 candidates.length 的每一个元素：
如果当前元素与前一个元素相同，则跳过，以避免重复组合（排序过了）。
如果当前元素大于 target，直接剪枝，跳出循环。
否则，将当前元素加入组合列表 combination，递归调用 backtrack，判断这组数字是否符合条件。
如果不符合，回溯，撤销当前选择，继续尝试下一个元素。
运行效率也很不错。直接击败了 99.87% 的选手。
这其中的关键代码有五处。
第一处，对数组进行排序，以便于后续跳过重复元素：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
Arrays.sort(candidates); // 排序以便于跳过重复元素
第二处，跳过同一层中重复的元素：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
if (i > start && candidates[i] == candidates[i - 1]) {
continue;
}
比如说 [1,1,2,2] 这种，如果 target 是 4，那么第二个 2 的时候，就不需要再递归了。
结果就只有 [1,1,2] 和 [2,2]。
第三处，剪枝操作，当前候选数大于剩余目标值，直接返回：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
if (candidates[i] > target) {
break;
}
比如说 [1, 1, 2, 5, 6, 7]，目标值是 8，如果当前数字是 5，那么剩余的目标值是 4，而 5 已经大于 4 了，所以直接返回。
第四处，递归调用时，下一次递归的起点要从当前元素的下一个元素开始：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
backtrack(candidates, target - candidates[i], i + 1, combination);
比如说 [1, 1, 2, 5, 6, 7]，目标值是 8，如果之前数字是 1+1+2，那么下一次递归的起点应该是 5，也就是从 2 的下一个元素开始。
第五处，回溯，撤销最后的选择：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
combination.remove(combination.size() - 1); // 回溯，撤销最后的选择
比如说 [1, 1, 2, 5, 6, 7]，目标值是 8，如果当前数字是 5，前面是 1+1+2，返回后需要从 1+1 开始尝试，撤销 2 这个选择。从 1+1+5 开始尝试。
总结
这道题和 039.组合总和 是姊妹篇，但要求不同，上一个是可以重复选择一个数，这次是有重复元素，但是同一个数字只能使用一次。
本质上还是一个回溯的问题，但需要跳过同一层的重复元素。
力扣链接：https://leetcode.cn/problems/combination-sum-ii/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
PDF 版本目前只针对二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 加入我们吧。
一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 5900 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！
语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
这道题可以说完全重写了，给出 1 道大家完全都能掌握的题解（ 主要是理解递归）。
增加代码注释，这样大家更容易看懂并掌握题解；
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
增加手绘图，这样大家更容易理解解题思路；
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。