40. 组合总和 II

二哥说，今天去帮父亲干了半天的活，一身尘埃，但是感觉很充实，累但知道了

生活的不易，更需要去珍惜现在拥有的一切，所以马不停蹄地继续刷题，今天的

题目是组合总和 II，这道题目是一道中等难度的题目，但是，只要我们细心分

析，就能迎刃而解。

题意

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有

可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

难度

中等

示例

输入: 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 中可能会存在有重复的数字。

同样我们也可以使用暴力，枚举所有的可能性，然后判断是否符合条件，如果符合条件就

加入到答案中。

class Solution04001 {

public List<List<Integer>> combinationSum2(int[] candidates, int target) {

List<List<Integer>> result = new ArrayList<>();

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 方法也是可以得出结果的。

040.组合总和 II-20240804185133.png

但是很遗憾，放在 LeetCode 上跑的时候，会发现超时了。

040.组合总和 II-20240804185205.png

问题就在于，重复计算太多，和 039.组合总和 一样，我们需要优化。

分析 2

优化的思路和 039.组合总和 是一样的，我们可以先对数组进行排序，然后在递归的时

候：

• 如果当前数字和上一个数字相同，我们直接跳过。

• 如果当前候选数字大于剩余的目标值，我们直接返回，然后进行剪枝操作。比如说

[1, 1, 2, 5, 6, 7]，目标值是 8，如果当前数字是 5，那么剩余的目标值是 4，而 5 已

经大于 4 了，所以直接返回。然后把 2 剪枝掉，因为 1+1+2+后面任何一个数都不满

足要求了。

好，我们来看题解：

class Solution04002 {

private List<List<Integer>> result = new ArrayList<>();

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% 的选手。

040.组合总和 II-20240804190003.png

这其中的关键代码有五处。

第一处，对数组进行排序，以便于后续跳过重复元素：

Arrays.sort(candidates); // 排序以便于跳过重复元素

第二处，跳过同一层中重复的元素：

if (i > start && candidates[i] == candidates[i - 1]) {

continue;

}

比如说 [1,1,2,2] 这种，如果 target 是 4，那么第二个 2 的时候，就不需要再递归了。

结果就只有 [1,1,2] 和 [2,2]。

第三处，剪枝操作，当前候选数大于剩余目标值，直接返回：

if (candidates[i] > target) {

break;

}

比如说 [1, 1, 2, 5, 6, 7]，目标值是 8，如果当前数字是 5，那么剩余的目标值是 4，而 5

已经大于 4 了，所以直接返回。

第四处，递归调用时，下一次递归的起点要从当前元素的下一个元素开始：

backtrack(candidates, target - candidates[i], i + 1, combination);

比如说 [1, 1, 2, 5, 6, 7]，目标值是 8，如果之前数字是 1+1+2，那么下一次递归的起点

应该是 5，也就是从 2 的下一个元素开始。

第五处，回溯，撤销最后的选择：

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/