代码随想录算法训练营第二十二天|leetcode17、216题-leetcode第216题

class Solution {
private:
    vector<vector<int>> result; // 存放结果集
    vector<int> path; // 符合条件的结果

    // backtracking函数用于递归搜索符合条件的组合
    // targetSum：目标和，也就是题目中的n。
    // k：题目中要求k个数的集合。
    // sum：已经收集的元素的总和，也就是path里元素的总和。
    // startIndex：下一层for循环搜索的起始位置。
    void backtracking(int targetSum, int k, int sum, int startIndex) {
        // 当path的大小等于k时，表示已经找到了一个符合条件的组合
        if (path.size() == k) {
            // 如果该组合的元素总和等于目标和，则将其加入结果集中
            if (sum == targetSum)
                result.push_back(path);
            return; // 如果path.size() == k 但sum != targetSum 直接返回
        }
        
        // 从startIndex开始循环搜索符合条件的数字
        for (int i = startIndex; i <= 9; i++) {
            sum += i; // 将当前数字i加入到sum中
            path.push_back(i); // 将当前数字i加入到path中
            // 递归搜索下一层，startIndex从i+1开始，避免重复使用数字
            backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndex
            sum -= i; // 回溯，将当前数字i从sum中移除
            path.pop_back(); // 回溯，将当前数字i从path中移除
        }
    }

public:
    // combinationSum3函数用于计算符合条件的组合
    vector<vector<int>> combinationSum3(int k, int n) {
        // 调用backtracking函数开始搜索符合条件的组合
        backtracking(n, k, 0, 1);
        // 返回结果集
        return result;
    }
};