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;}
};