找出全部相加之和为 n 的 k 个数的组合。组合中只容许含有 1 - 9 的正整数,而且每种组合中不存在重复的数字。web
说明:
全部数字都是正整数。
解集不能包含重复的组合。
示例 1:算法
输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:svg
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]code
class Solution { vector<vector<int>> result; void backtrace(vector<int>&tmp,int k,int n,int cur){ if(tmp.size() == k){ if(n == 0) result.push_back(tmp); return; } int average = n / (k - tmp.size()); for(;cur < 10;++cur){ if(cur > average) break; tmp.push_back(cur); backtrace(tmp,k,n - cur,cur + 1); tmp.pop_back(); } } public: vector<vector<int>> combinationSum3(int k, int n) { vector<int> tmp; backtrace(tmp,k,n,1); return result; } };