代码解决
class Solution { public: vector<vector<int>> result; // 存储所有符合条件的组合 vector<int> res; // 当前组合 // 回溯函数 void backtracing(int k, int n, int index, int sum) { // 如果当前组合的长度等于k，且总和等于n if (res.size() == k && sum == n) { result.push_back(res); return; } // 如果当前组合的长度超过k，或总和超过n，剪枝返回 if (res.size() > k || sum > n) { return; } // 从index开始遍历1到9的数字 for (int i = index; i <= 9; ++i) { res.push_back(i); // 将当前数字加入组合 backtracing(k, n, i + 1, sum + i); // 递归调用回溯函数 res.pop_back(); // 回溯，移除最后一个加入的数字 } } // 主函数 vector<vector<int>> combinationSum3(int k, int n) { backtracing(k, n, 1, 0); // 从1开始回溯 return result; // 返回所有符合条件的组合 } };类和成员变量
class Solution: 定义了一个解决方案类。vector<vector<int>> result: 用于存储所有满足条件的组合结果。每个组合都是一个整数数组。vector<int> res: 用于存储当前的组合。随着回溯的进行，这个向量会不断变化。方法：
backtracing
参数:
int k: 组合中数字的个数。int n: 目标和。int index: 当前选择数字的起始位置，防止重复选择。int sum: 当前组合的数字和。逻辑:
- 结束条件:
if (res.size() == k && sum == n): 当当前组合的长度等于k且总和等于n时，将当前组合添加到结果集中。if (res.size() > k || sum > n): 当当前组合的长度超过k或总和超过n时，直接返回，不再进行后续计算，这是剪枝操作，减少不必要的计算。- 循环遍历:
for (int i = index; i <= 9; ++i): 遍历从index到9的数字。index确保了每次递归时不重复选择已经选择过的数字。res.push_back(i): 将当前数字i添加到当前组合res中。backtracing(k, n, i + 1, sum + i): 递归调用回溯函数，i + 1确保下一个数字从当前数字的下一个开始，sum + i更新当前组合的和。res.pop_back(): 回溯时，将最后一个加入的数字移除，以便进行下一次组合。方法：
combinationSum3
- 逻辑:
- 调用
backtracing(k, n, 1, 0)从数字1开始查找组合。return result: 返回存储结果的result。回溯算法解释
回溯算法是一种系统地搜索问题解的算法，适用于满足特定条件的所有解。在这个问题中，回溯用于从数字1到9中选出k个数，使它们的和为n。每次递归调用都会在当前组合中添加一个新的数字，并继续尝试加入更多数字，直到满足条件或不满足条件而进行剪枝。通过回溯和剪枝，可以有效地找到所有满足条件的组合。
剪枝
class Solution { private: vector<vector<int>> result; // 存放结果集 vector<int> path; // 符合条件的结果 void backtracking(int targetSum, int k, int sum, int startIndex) { if (sum > targetSum) { // 剪枝操作 return; } if (path.size() == k) { if (sum == targetSum) result.push_back(path); return; // 如果path.size() == k 但sum != targetSum 直接返回 } for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) { // 剪枝 sum += i; // 处理 path.push_back(i); // 处理 backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndex sum -= i; // 回溯 path.pop_back(); // 回溯 } } public: vector<vector<int>> combinationSum3(int k, int n) { result.clear(); // 可以不加 path.clear(); // 可以不加 backtracking(n, k, 0, 1); return result; } };
