39. 组合总和

039.组合总和

鲁迅没说过：今天是周六，但不影响我继续刷一道二哥的 LeetCode 刷题笔记。

遇到组合这种题，无非就是遍历、递归、回溯，多练习几次就能掌握了。

题意

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates

中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意

顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制 重复 被选取。如果至少一个数字的被选数量不

同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

难度

中等

示例

输入：candidates = [2,3,6,7], target = 7

输出：[[2,2,3],[7]]

解释：

2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。

7 也是一个候选， 7 = 7 。

仅有这两种组合。

输入: candidates = [2,3,5], target = 8

输出: [[2,2,2,2],[2,3,3],[3,5]]

输入: candidates = [2], target = 1

输出: []

分析 1

说实话，这道题目描述了很多，都不如看一个示例，一看就懂。

从示例中可以看得出来，这道题需要我们从整数数组中不断地排列组合，找出所有符合要

求的答案。

并且可以重复使用数组中的元素。和之前的两数之和，三数之和有类似的地方。

最容易想到的办法就是一个个枚举，然后判断是否符合条件，如果符合条件就加入到答案

中。

class Solution03901 {

// 主方法，找到所有组合，使得组合中数字的和为目标值 target

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

// 初始化结果列表，用于存储所有符合条件的组合

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

// 调用辅助方法，生成所有可能的组合

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) {

result.add(new ArrayList<>(combination));

return;

}

// 循环遍历从 start 到 candidates.length 的每一个元素

for (int i = start; i < candidates.length; i++) {

// 将当前元素加入组合列表

combination.add(candidates[i]);

// 递归调用辅助方法，继续生成可能的组合

generateAllCombinations(candidates, target, combination, result, i);

// 回溯，撤销当前选择，继续尝试下一个元素

combination.remove(combination.size() - 1);

}

}

// 主程序入口，用于测试

public static void main(String[] args) {

Solution03901 solution = new Solution03901();

// 定义候选数组和目标值

int[] candidates = {2, 3, 6, 7};

int target = 7;

// 调用主方法，找到所有符合条件的组合

List<List<Integer>> result = solution.combinationSum(candidates, target);

// 输出结果

System.out.println("所有组合: " + result);

}

}

对于辅助方法 generateAllCombinations，整体的思路是：

1. 计算当前组合的和 sum，通过流操作计算 combination 中所有元素的和。一开始是

0。

2. 如果 sum 大于 target，说明当前组合的和已经超过了目标值，直接返回。

3. 如果 sum 等于 target，说明当前组合的和等于目标值，将当前组合添加到结果列表

中，然后返回。注意不要直接添加 combination，而是添加一个新的 ArrayList。

（new ArrayList<>(combination)）

4. 循环遍历从 start 到 candidates.length 的每一个元素。将当前元素 candidates[i] 加入

组合列表 combination，递归调用 generateAllCombinations 方法，继续生成可能的组

合。如果不符合要求，就回溯，撤销当前选择，继续尝试下一个元素。

这里的循环遍历和回溯非常重要，如果一开始没有看懂，可以放到 IDEA 中 debug 调试跑

一边，看看每一步的执行过程。

039.组合总和-20240803201305.png

尤其是 combination 的变化，这个变化是整个递归的核心，需要仔细体会。

然后来看一下整体的题解效率。

039.组合总和-20240803201403.png

不高，但容易理解。

分析 2

暴力效率低的原因是，有很多没必要的计算，比如说输入是 [2, 3, 6, 7]，目标值是 7，那

么我们在计算 2 + 2 + 3 符合条件后，就没必要再计算 2 + 2 + 6 和 2 + 2 + 7 了。

因为 6 和 7 都比 3 大。

但暴力解法是一个个枚举，没有考虑这个问题。

好，我们需要来解决这个问题。

class Solution {

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

public List<List<Integer>> combinationSum(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 (candidates[i] > target) {

break; // 当前候选数大于剩余目标值，剪枝

}

combination.add(candidates[i]);

backtrack(candidates, target - candidates[i], i, combination); // 因为可以重复

使用当前数字，所以传入 i 而不是 i + 1

combination.remove(combination.size() - 1); // 回溯，撤销最后的选择

}

}

}

这里的主要改进是：

①、对 candidates 数组进行排序。

②、在递归调用回溯方法 backtrack 之前，先判断 candidates[i] 是否大于剩余的 target，

如果大于，就直接 break，不再继续递归。

039.组合总和-20240803202948.png

比如说 [2,2,6] 这个组合就会被剪枝。

当然了，这是建立在 backtrack(candidates, target - candidates[i], i, combination); 的

基础上，我们把 target 减去了 candidates[i]，在寻找组合的时候，将目标值不断地减

小，直到等于 0。

这样效率就会提升很多，我们来看一下。

039.组合总和-20240803212351.png

总结

这道题目的难点在于如何避免重复的计算，因为可以重复使用数组中的元素，所以需要在

递归调用的时候，对一些重复的计算进行剪枝。

这样效率就会提升很多。总体上算法的难度不高，主要在于回溯的思想，需要多练习。

力扣链接：https://leetcode.cn/problems/combination-sum/