个人主页代码不加冰欢迎来访作者简介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 4k 4的话那么第一层for循环的时候从元素2开始的遍历都没有意义了。 在第二层for循环从元素3开始的遍历都没有意义了。这么说有点抽象如图所示图中每一个节点图中为矩形就代表本层的一个for循环那么每一层的for循环从第二个数开始遍历的话都没有意义都是无效遍历。所以可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了那么就没有必要搜索了。注意代码中i就是for循环里选择的起始位置。for (int i startIndex; i n; i) {接下来看一下优化过程如下已经选择的元素个数path.size();所需需要的元素个数为: k - path.size();列表中剩余元素n-i 所需需要的元素个数k - path.size()在集合n中至多要从该起始位置 : i n - (k - path.size()) 1开始遍历为什么有个1呢因为包括起始位置我们要是一个左闭的集合。举个例子n 4k 3 目前已经选取的元素为0path.size为0n - (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); } }剪枝原理假设 n4, k3当前 path.size()1还需要选2个 start3时可选 [3,4] 刚好2个 → 可以 start4时只剩 [4] 只有1个 → 不够不用试了 临界值 n - (k - path.size()) 1 4 - 2 1 3 所以 i 3 即可优化版本class Solution { ListListInteger result new ArrayList(); LinkedListInteger path new LinkedList(); public ListListInteger 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个不同的数字我们可以得到的最小和是1234 10因为10 1没有有效的组合。提示:2 k 91 n 60题目分析拿到这道题目我们会感到很熟悉因为这其实跟我们前面刚做完的77题没什么大的区别整体还是回溯算法同时也可以进行剪枝优化只不过条件变了一点多了一个限制本题是要找到和为n的k个数的组合而整个集合已经是固定的了[1,...,9]。与77题的区别对比项77题组合216题组合总和III数字范围1 ~ n1 ~ 9固定目标凑够 k 个数凑够 k 个数且和为 n剪枝条件剩余数量不够数量不够和已超过目标初步思路例如 k 2n 4的话就是在集合[1,2,3,4,5,6,7,8,9]中求 k个数 2, n和 4的组合。选取过程如图图中可以看出只有最后取到集合13和为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); // 注意i1调整startIndex sum - i; // 回溯 path.pop_back(); // 回溯 }和回溯算法组合问题再剪剪枝 一样for循环的范围也可以剪枝i 9 - (k - path.size()) 1就可以了。题目答案class Solution { ListListInteger result new ArrayList(); ListInteger path new ArrayList(); int sum 0; // 当前path中所有数的和 public ListListInteger 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; } } }结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励