首页 > 代码库 > Combination Sum III -- leetcode
Combination Sum III -- leetcode
Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Ensure that numbers within the set are sorted in ascending order.
Example 1:
Input: k = 3, n = 7
Output:
[[1,2,4]]
Example 2:
Input: k = 3, n = 9
Output:
[[1,2,6], [1,3,5], [2,3,4]]
Credits:
基本思路：
使用dfs进行穷举遍历。
因为结果集要求按升序排列，则先选择较小的数字，然后从剩下的较大数中进行选择。
确保每次选择的数都大于上次选择的。
class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> ans;
vector<int> seq;
helper(ans, seq, k, n);
return ans;
}
void helper(vector<vector<int>>& ans, vector<int>& seq, int k, int n) {
if (!k && !n)
return ans.push_back(seq);
if (!k || n<0)
return;
int start = seq.empty() ? 1 : seq.back()+1;
for (int i=start; i<=9; i++) {
seq.push_back(i);
helper(ans, seq, k-1, n-i);
seq.pop_back();
}
}
};Combination Sum III -- leetcode
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。