191.回溯算法：组合总和|||（力扣）

代码解决

class Solution {
public:
    vectorint>> 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();  // 回溯，移除最后一个加入的数字
        }
    }
 
    // 主函数
    vectorint>> combinationSum3(int k, int n) {
        backtracing(k, n, 1, 0);  // 从1开始回溯
        return result;  // 返回所有符合条件的组合
    }
};

类和成员变量

• class Solution: 定义了一个解决方案类。
• vector> result: 用于存储所有满足条件的组合结果。每个组合都是一个整数数组。
• vector 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:
    vectorint>> 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:
    vectorint>> combinationSum3(int k, int n) {
        result.clear(); // 可以不加
        path.clear();   // 可以不加
        backtracking(n, k, 0, 1);
        return result;
    }
};