题解 | #加起来和为目标值的组合(三)#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param k int整型 
     * @param n int整型 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > combination(int k, int n) {
        vector<vector<int>> res;
        vector<int> path;
        dfs(k, n, 0, 1, path, res);
        return res;
        // write code here
    }
    void dfs(int k, int n, int cur_sum, int index, vector<int>& path, vector<vector<int>>& res){
        if(path.size()==k && cur_sum==n){
            res.push_back(path);
            return;
        }// 剪枝
        for(int i=index; i<=9&&n-(k-path.size())+1; i++){
            path.push_back(i);
            cur_sum += i;
            dfs(k, n, cur_sum, i+1, path, res);
            cur_sum -= i;
            path.pop_back();
        }
    }
};
https://www.programmercarl.com/0216.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CIII.html#%E5%89%AA%E6%9E%9D