找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。
说明:
所有数字都是正整数。
解集不能包含重复的组合。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/combination-sum-iii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路:
代码:
class Solution {
private:
vector<vector<int> > ans;
vector<int> temp;
set<vector<int> > setAns;
int k;
public:
// 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。
vector<vector<int> > combinationSum3(int k, int n) {
this->k = k;
dfs(1, 0, n);
for (auto it = setAns.begin(); it != setAns.end(); ++it) {
ans.push_back(*it);
}
return ans;
}
// pos代表是否要加上的数字 范围从1~9递增 num表示已经加入临时队列的数字个数
/// target表示要达到的目标
void dfs(int pos, int num, int target){
// cout << "当前判断pos:" << pos << ",当前num:" << num <<endl;
if (num == k && target == 0) {// 满足条件
// cout << "满足条件" << endl;
setAns.insert(temp);
return;
}
if (num > k || pos >= 10) {// 队列数字多于k个 或者 要加上的数字大于等于10了
// cout << "num > k || pos >= 10" << endl;
// cout << "num:" << num << endl;
return;
}
if (num == k && target > 0) {
// cout << "num == k && target > 0" << endl;
return;
}
// num < k 选择是否加上当前数字
// 加上当前数字
if (pos <= target) {
// cout << "加上当前数字"<< pos<< ",target:" << target-pos << endl;
temp.push_back(pos);
for (int nextNum = pos+1; nextNum <= 10; ++nextNum) {
dfs(nextNum, num+1, target-pos);
}
temp.pop_back();
}
// 不加上当前数字
// cout << "不加上当前数字" << pos<< ",target:" << target<< endl;
dfs(pos+1, num, target);
}
};