216.Combination Sum III

 class Solution {
public:
    vector<vector<int> > combinationSum3(int k, int n) {
        vector<vector<int> > res;
        vector<int> out;
        combinationSum3DFS(k, n, 1, out, res);
        return res;
    }
    void combinationSum3DFS(int k, int n, int level, vector<int> &out, vector<vector<int> > &res) {
        if (n < 0) return;
        if (n == 0 && out.size() == k) res.push_back(out);
        for (int i = level; i <= 9; ++i) {
            out.push_back(i);
            combinationSum3DFS(k, n - i, i + 1, out, res);
            out.pop_back();
        }
    }
};
class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int> out;
        vector<vector<int> > res;
        combinationSumDFS(1,k,n,out,res);
        return res;
    }
    void combinationSumDFS(int s,int k, int n, vector<int> &out, vector<vector<int> > &res) {
        if (k==0 && n==0){
            res.push_back(out);
        }
        else if(k>0 && n>0){
            for (int i = s; i < 10; ++i) {
                out.push_back(i);
                combinationSumDFS(i+1,k-1, n-i,  out, res);
                out.pop_back();
            }
        }
    }

};