dfs搜索

组合数枚举的变形，组合数需要传入一个start参数，每次从start开始枚举。

新增了一个和的要求，我们只需要在搜索的过程当中不仅记录路径，顺便记录和即可。

时间复杂度指数级别

AC代码

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;

    void dfs(int u, int k,int start, int s, int n) {
        if (u == k) {
            if (s == n) 
                res.push_back(path);
            return ;
        }

        for (int i = start ; i <= 9 ; i ++) {
            path.push_back(i);
            dfs(u + 1, k, i + 1, s + i,n);
            path.pop_back();
        }
    }

    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(0, k, 1, 0, n);
        return res;
    }
};