039.组合总和

作者：沉默王二
发布时间：2024-08-03T21:32:26.202+0800

鲁迅没说过：今天是周六，但不影响我继续刷一道二哥的 LeetCode 刷题笔记。遇到组合这种题，无非就是遍历、递归、回溯，多练习几次就能掌握了。

题意

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。

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

难度

中等

示例

textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
输入：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

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

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

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

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

textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
class Solution03901 {
    // 主方法，找到所有组合，使得组合中数字的和为目标值 target
    public List<List> combinationSum(int[] candidates, int target) {
        // 初始化结果列表，用于存储所有符合条件的组合
        List<List> result = new ArrayList<>();
        // 调用辅助方法，生成所有可能的组合
        generateAllCombinations(candidates, target, new ArrayList<>(), result, 0);
        // 返回结果列表
        return result;
    }

    // 辅助方法，递归生成所有可能的组合
    private void generateAllCombinations(int[] candidates, int target, List combination, List<List> 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> result = solution.combinationSum(candidates, target);
        // 输出结果
        System.out.println("所有组合: " + result);
    }
}

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

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

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

如果 sum 等于 target，说明当前组合的和等于目标值，将当前组合添加到结果列表中，然后返回。注意不要直接添加 combination，而是添加一个新的 ArrayList。（new ArrayList<>(combination)）

循环遍历从 start 到 candidates.length 的每一个元素。将当前元素 candidates[i] 加入组合列表 combination，递归调用 generateAllCombinations 方法，继续生成可能的组合。如果不符合要求，就回溯，撤销当前选择，继续尝试下一个元素。

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

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

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

不高，但容易理解。

分析 2

暴力效率低的原因是，有很多没必要的计算，比如说输入是 [2, 3, 6, 7]，目标值是 7，那么我们在计算 2 + 2 + 3 符合条件后，就没必要再计算 2 + 2 + 6 和 2 + 2 + 7 了。

因为 6 和 7 都比 3 大。

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

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

textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
class Solution {
private List<List> result = new ArrayList<>();

    public List<List> 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 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，不再继续递归。

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

当然了，这是建立在 backtrack(candidates, target - candidates[i], i, combination); 的基础上，我们把 target 减去了 candidates[i]，在寻找组合的时候，将目标值不断地减小，直到等于 0。

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

总结

这道题目的难点在于如何避免重复的计算，因为可以重复使用数组中的元素，所以需要在递归调用的时候，对一些重复的计算进行剪枝。

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

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

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对二哥编程星球的球友开放，如果你也想一起打卡学习算法的话，戳链接加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球（目前已有 5900 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu

这道题可以说完全重写了，给出 1 道大家完全都能掌握的题解（主要是理解递归）。

增加代码注释，这样大家更容易看懂并掌握题解；

增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；

增加手绘图，这样大家更容易理解解题思路；

增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；

增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；

图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。

另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

技术派阅读地址：https://paicoding.com/column/7/39