【LeetCode刷题日记】77216.回溯算法剪枝优化在组合问题中的应用

🔥个人主页：代码不加冰（欢迎来访）
🎬作者简介：java后端学习者
❄️个人专栏：LeetCode刷题日记 ， 苍穹外卖日记，SSM框架深入，JavaWeb，
✨命运的结局尽可永在，不屈的挑战却不可须臾或缺！

前言：

大家好，我是代码不加冰，今天又到了我们每日的刷题环节，依旧是回溯算法的专题，让我们一起看看吧，这篇文章主要是对回溯算法的剪枝操作进行分析，回溯算法有时候也是可以进行适当优化的。

摘要：

本文通过LeetCode 77.组合和216.组合总和III两道题目，分析了回溯算法中的剪枝优化技巧。在组合问题中，当剩余数字不足以凑满k个元素时，可提前终止循环，将遍历范围限制为i <= n-(k-path.size())+1。在组合总和问题中，除了数量剪枝外，当当前和已超过目标值时也可提前剪枝。文章通过具体示例和代码演示了这两种剪枝方法的应用，显著提高了算法效率。优化后的回溯算法避免了无效搜索，在处理组合类问题时更具优势。

题目背景：77.组合优化

我们在前面利用单纯的回溯算法进行暴力拆解了组合 的问题，但是在执行的过程中，我们发现还是有地方可以进行剪枝优化的。

在遍历的过程中有如下代码：

for (int i = startIndex; i <= n; i++) { path.push_back(i); backtracking(n, k, i + 1); path.pop_back(); }

这个遍历的范围是可以剪枝优化的，怎么优化呢

来举一个例子，n = 4，k = 4的话，那么第一层for循环的时候，从元素2开始的遍历都没有意义了。 在第二层for循环，从元素3开始的遍历都没有意义了。

这么说有点抽象，如图所示：

图中每一个节点（图中为矩形），就代表本层的一个for循环，那么每一层的for循环从第二个数开始遍历的话，都没有意义，都是无效遍历。

所以，可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。

如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。

注意代码中i，就是for循环里选择的起始位置。

for (int i = startIndex; i <= n; i++) {

接下来看一下优化过程如下：

1. 已经选择的元素个数：path.size();

2. 所需需要的元素个数为: k - path.size();

3. 列表中剩余元素（n-i） >= 所需需要的元素个数（k - path.size()）

4. 在集合n中至多要从该起始位置 : i <= n - (k - path.size()) + 1，开始遍历

为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。

举个例子，n = 4，k = 3， 目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。

从2开始搜索都是合理的，可以是组合[2, 3, 4]。

所以优化之后的for循环是：

for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置

因此：

当剩余可选数字不够凑满k个时，可以提前停止循环。

java private void backtrack(int n, int k, int start) { if (path.size() == k) { result.add(new ArrayList<>(path)); return; } // 剪枝优化： // 还需要选的数量 = k - path.size() // 最多能从 start 到 n - (k - path.size()) + 1 for (int i = start; i <= n - (k - path.size()) + 1; i++) { path.add(i); backtrack(n, k, i + 1); path.remove(path.size() - 1); } }

剪枝原理：

假设 n=4, k=3，当前 path.size()=1（还需要选2个） start=3时：可选 [3,4] 刚好2个 → 可以 start=4时：只剩 [4] 只有1个 → 不够，不用试了 临界值 = n - (k - path.size()) + 1 = 4 - 2 + 1 = 3 所以 i <= 3 即可

优化版本：

class Solution { List<List<Integer>> result = new ArrayList<>(); LinkedList<Integer> path = new LinkedList<>(); public List<List<Integer>> combine(int n, int k) { combineHelper(n, k, 1); return result; } /** * 每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠startIndex * @param startIndex 用来记录本层递归的中，集合从哪里开始遍历（集合就是[1,...,n] ）。 */ private void combineHelper(int n, int k, int startIndex){ //终止条件 if (path.size() == k){ result.add(new ArrayList<>(path)); return; } for (int i = startIndex; i <= n - (k - path.size()) + 1; i++){ path.add(i); combineHelper(n, k, i + 1); path.removeLast(); } } }

题目背景：216.组合总和Ⅱ

找出所有相加之和为n的k个数的组合，且满足下列条件：

• 只使用数字1到9
• 每个数字最多使用一次

返回所有可能的有效组合的列表。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:

输入:k= 3,n= 7输出:[[1,2,4]]解释:1 + 2 + 4 = 7 没有其他符合的组合了。

示例 2:

输入:k= 3,n= 9输出:[[1,2,6], [1,3,5], [2,3,4]]解释:1 + 2 + 6 = 9 1 + 3 + 5 = 9 2 + 3 + 4 = 9 没有其他符合的组合了。

示例 3:

输入:k = 4, n = 1输出:[]解释:不存在有效的组合。 在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

提示:

• 2 <= k <= 9
• 1 <= n <= 60

题目分析：

拿到这道题目，我们会感到很熟悉，因为这其实跟我们前面刚做完的77题没什么大的区别，整体还是回溯算法，同时也可以进行剪枝优化，只不过条件变了一点，多了一个限制，本题是要找到和为n的k个数的组合，而整个集合已经是固定的了[1,...,9]。

与77题的区别

初步思路：

例如 k = 2，n = 4的话，就是在集合[1,2,3,4,5,6,7,8,9]中求 k（个数） = 2, n（和） = 4的组合。

选取过程如图：

图中，可以看出，只有最后取到集合（1，3）和为4 符合条件

优化思路：

这道题目，剪枝操作其实是很容易想到了，想必大家看上面的树形图的时候已经想到了。

如图：

已选元素总和如果已经大于n（图中数值为4）了，那么往后遍历就没有意义了，直接剪掉。

那么剪枝的地方可以放在递归函数开始的地方，剪枝代码如下：

if (sum > targetSum) { // 剪枝操作 return; }

当然这个剪枝也可以放在 调用递归之前，即放在这里，只不过要记得 要回溯操作给做了。

for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) { // 剪枝 sum += i; // 处理 path.push_back(i); // 处理 if (sum > targetSum) { // 剪枝操作 sum -= i; // 剪枝之前先把回溯做了 path.pop_back(); // 剪枝之前先把回溯做了 return; } backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndex sum -= i; // 回溯 path.pop_back(); // 回溯 }

和回溯算法：组合问题再剪剪枝 一样，for循环的范围也可以剪枝，i <= 9 - (k - path.size()) + 1就可以了。

题目答案：

class Solution { List<List<Integer>> result = new ArrayList<>(); List<Integer> path = new ArrayList<>(); int sum = 0; // 当前path中所有数的和 public List<List<Integer>> combinationSum3(int k, int n) { backtrack(k, n, 1); return result; } private void backtrack(int k, int n, int start) { // 剪枝1：如果当前和已经大于n，没必要继续（因为后面数字更大） if (sum > n) { return; } // 终止条件：path中已经有k个数了 if (path.size() == k) { if (sum == n) { result.add(new ArrayList<>(path)); } return; } // 横向遍历：从start到9 // 剪枝2：剩余可选数不够凑满k个时停止 for (int i = start; i <= 9 - (k - path.size()) + 1; i++) { // ① 做选择 path.add(i); sum += i; // ② 递归 backtrack(k, n, i + 1); // ③ 撤销选择 path.remove(path.size() - 1); sum -= i; } } }

结语：

如果对你有帮助，请点赞，关注，收藏，你的支持就是我最大的鼓励！