Find all valid combinations of k numbers that sum up to n such that the following conditions are true:
Only numbers 1 through 9 are used.
Each number is used at most once.
Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.
voiddfs(int k, int n, vector<vector<int>>& res, vector<int>& tmp, int st){ if(!k and !n) res.push_back(tmp); if(!k or !n) return; int cmp = 0; for(int i = 9; i >= st and i > 9 - k; i--) cmp += i; if(cmp < n) return; for(int i = st; i <= 9and i <= n; i++) { tmp.push_back(i); dfs(k-1, n-i, res, tmp, i+1); tmp.pop_back(); } } };