class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        solution.clear();
        answer.clear();
        if(k>9||n>45)
            return solution;
        deal(1,k,n);
        return solution;
    }
    void deal(int begin,int remain,int target)
    {
        if(target==0&&remain==0)
        {
            solution.push_back(answer);
            return;
        }

        for(int i=begin;i<=9&&target>=i;++i)
        {
            answer.push_back(i);
            deal(i+1,remain-1,target-i);
            answer.pop_back();
        }
    }
    vector<int> answer;
    vector<vector<int>> solution;
};