刷代码随想录有感（67）：回溯算法——组合总和

题干：

代码：

class Solution {
public:
    vector<int>tmp;
    vector<vector<int>>res;
    void backtracking(int k, int n, int sum, int start){
        if(tmp.size() == k && sum == n){
            res.push_back(tmp);
            return;
        }
        for(int i = start; i <= 9; i++){
            sum += i;
            tmp.push_back(i);
            backtracking(k, n, sum, i + 1);
            sum -= i;
            tmp.pop_back();
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        backtracking(k, n, 0, 1);
        return res;
    }
};

剪枝：如果sum > n 则终止， 如果取不到k个数则终止：

class Solution {
public:
    vector<int>tmp;
    vector<vector<int>>res;
    void backtracking(int k, int n, int sum, int start){
        if(sum > n)return;//剪枝1
        if(tmp.size() == k && sum == n){
            res.push_back(tmp);
            return;
        }
        for(int i = start; i <= 9 - (k - tmp.size()) + 1; i++){//剪枝2
            sum += i;
            tmp.push_back(i);
            backtracking(k, n, sum, i + 1);
            sum -= i;
            tmp.pop_back();
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        backtracking(k, n, 0, 1);
        return res;
    }
};

回溯调用参数不是start而是i  + 1...