从回溯法到剪枝优化： 找出相加之和为 n 的 k 个数的组合

从回溯法到剪枝优化： 找出相加之和为 n 的 k 个数的组合

在这篇博客中，我们将深入探讨一个经典的算法问题——从数字1到9中找出相加之和为n的k个数的组合。这个问题需要注意组合内的数字不可重复使用，且每个数字只能使用一次。

1. 问题描述

题目要求如下：

• 给定两个整数 k 和 n，需要从数字 1 到 9 中找出 k 个不重复的数字，且它们的和为 n。
• 每个数字最多使用一次，返回所有可能的有效组合。

示例：

示例 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
• 输出: []
• 解释: 由于我们需要选择4个不同的数字，且最小的可能组合和是 1 + 2 + 3 + 4 = 10，明显大于1，因此没有有效组合。

216. 组合总和 III - 力扣（LeetCode）

2. 初步思路——回溯法

本问题最直观的解法是通过回溯法，即遍历所有可能的组合，并在符合条件时将其加入结果列表。

初步实现：

class Solution {
public:vector<vector<int>> ans;void backtrack(int k, int n, vector<int>& comb, int cur, int sum) {if (comb.size() == k) {if (sum == n) {ans.push_back(comb);}return;}for (int i = cur + 1; i < n; i++) {sum += i;comb.push_back(i);backtrack(k, n, comb, i, sum);comb.pop_back();sum -= i;}}vector<vector<int>> combinationSum3(int k, int n) {vector<int> comb;backtrack(k, n, comb, 0, 0);return ans;}
};

问题分析：

• 问题 1: for 循环的范围设定为 cur + 1 到 n，实际上题目中要求只使用1到9之间的数字，因此多余的循环会导致性能低下。
• 问题 2: 没有进行剪枝优化，导致大量无效计算。例如，若当前组合的和已经大于 n，我们可以立即结束递归。

3. 性能优化——剪枝和范围控制

为了提高算法效率，必须对遍历的范围和条件进行合理控制，避免不必要的递归调用。以下是优化的关键点：

1. 调整遍历范围：我们只需要在1到9的数字中进行选择。
2. 剪枝优化：当组合长度已经超过 k，或者和已经超过 n 时，可以直接停止递归。
3. 提前判断和剪枝：在 sum + i > n 的时候，可以提前退出当前循环，避免无效递归。

4. 优化后的代码

我们对代码进行如下优化：

class Solution {
public:vector<vector<int>> ans;// 回溯函数void backtrack(int k, int n, vector<int>& comb, int cur, int sum) {if (comb.size() == k) {if (sum == n) {ans.push_back(comb);}return;}if (sum > n) {return;}// 从 cur+1 开始，遍历数字1到9for (int i = cur + 1; i <= 9; i++) {if (sum + i > n) {break;  // 剪枝：如果当前数字加上去超过 n，则不再继续}comb.push_back(i);  // 选择当前数字backtrack(k, n, comb, i, sum + i);  // 递归到下一层comb.pop_back();  // 撤销选择}}vector<vector<int>> combinationSum3(int k, int n) {vector<int> comb;backtrack(k, n, comb, 0, 0);  // 从0开始递归return ans;}
};

5. 代码详解

• 回溯的基本思路：通过逐步选择1到9之间的数字，不断累加检查是否满足条件。如果符合条件（组合长度为 k 且和为 n），将该组合保存到结果中。
• 剪枝优化：
  • 当当前组合的和 sum 超过 n 时，继续选择没有意义，所以我们立即终止递归。
  • 当选择的数字加起来已经无法满足要求时，直接跳出循环，避免后续无效的递归。

6. 示例讲解

我们以示例 k = 3, n = 9 为例，详细解释优化后的代码执行过程：

• 初始状态：组合为空，当前和为0，递归从数字1开始。
• 选择数字1，组合变为 [1]，当前和为 1，继续递归。
• 选择数字2，组合变为 [1, 2]，当前和为 3，继续递归。
• 选择数字6，组合变为 [1, 2, 6]，当前和为 9，符合条件，将组合加入结果。
• 回溯后，继续探索其他组合，选择 [1, 3, 5] 和 [2, 3, 4]，同样满足条件并保存。
• 最终返回的结果为：[[1, 2, 6], [1, 3, 5], [2, 3, 4]]。

7. 总结

• 回溯法是解决此类组合问题的常用方法，但若不进行优化容易造成超时。
• 通过合理的剪枝优化，可以大幅减少无效计算，从而提高算法性能。
• 本题的解法适用于组合问题中的数字范围较小、数字不重复等特定约束场景。

希望通过对回溯法的详细分析和剪枝优化的讲解，能帮助你更好地理解如何解决这个问题。如果有其他更复杂的变体问题，我们可以继续讨论如何处理不同的约束条件。