191.回溯算法：组合总和|||（力扣）
代码解决
class Solution { public:vector<vector<int>> result; // 存储所有符合条件的组合vector<int> res; // 当前组合// 回溯函数void backtracing(int k, int n, int index, int sum) {// 如果当前组合的长度等于k，且总和等于nif (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调整startIndexsum -= i; // 回溯path.pop_back(); // 回溯}}public:vector<vector<int>> combinationSum3(int k, int n) {result.clear(); // 可以不加path.clear(); // 可以不加backtracking(n, k, 0, 1);return result;} };