class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> result;
vector<int> temp;
int local = 0;
dfs(result, temp, local, k, n, 1);
return result;
}
void dfs(vector<vector<int>> &result, vector<int> &temp, int &local, int &k, int &n, int index) {
if(temp.size() > k) {
return;
}
if(local == n && temp.size() == k) {
result.push_back(temp);
return;
}
for(int i = index; i <= 9 && local <= n; i++) {
temp.push_back(i);
local += i;
dfs(result, temp, local, k, n, i + 1);
local = i;
temp.pop_back();
}
}
};
C++ Solution using DFS and Recursion 0ms O(n^k)


I agree that the tree will have K levels, but not about children. Each tree node can have up to 9 children (because you've got up to 9 recursion calls) . So, tree levels will have at most 9, 99, ..., 9^k children respectively. So, in general up to O(k(9^k)) children in the tree. I think this is the complexity.