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