组合总和III
找出所有相加之和为 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]]
思路
与组合问题的思路类似，只是条件变了而已
直接上三部曲分析
1、确定递归函数的参数和返回值
这里仍然不需要返回值，因为我们是去操作一个"数组"
参数就是组合的元素个数k，目标相加和target以及控制遍历位置的beginIndex
依然需要两个数组来保存结果
class Solution {
private:
vector<int> path;
vector<vector<int>> res;
//确定递归函数的参数和返回值
void backtracking(int k, int target, int beginIndex){
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
}
};
2、确定终止条件
当遍历到叶子节点时触发终止条件，并判断此时target是否被减为0（这里找符合条件的元素和是通过减法来进行的，详见两数之和）
这里刚开始做容易乱，强调一下，在这个回溯模板中，终止条件一般就是深度，即path大小与k是否相等，相等就终止
（我做的时候还把target == 0也作为条件一块加上了，实际上是错误的，这个条件对应是否要保存当前path）
class Solution {
private:
vector<int> path;
vector<vector<int>> res;
//确定递归函数的参数和返回值
void backtracking(int k, int target, int beginIndex){
//终止条件
if(path.size() == k){//是否遍历到叶子节点
if(target == 0){
res.push_back(path);
return;
}
}
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
}
};
3、确定单层处理逻辑
在每层递归中，遍历规定范围内的值，用来与target作差，并保存当前遍历到的路径值
然后触发递归
在回溯过程中，将减掉的值再加回target，并pop掉path中保存的路径值
class Solution {
private:
vector<int> path;
vector<vector<int>> res;
//确定递归函数的参数和返回值
void backtracking(int k, int target, int beginIndex){
//终止条件
if(path.size() == k){//是否遍历到叶子节点
if(target == 0){//若target为0，则当前path中保存的路径值之和满足为n的条件
res.push_back(path);
return;
}
}
//确定单层处理逻辑
for(int i = beginIndex; i <= 9; ++i){
target -= i;//当前路径值与target作差
path.push_back(i);//保存当前路径值
backtracking(k, target, i + 1);//触发下层递归，跳过当前值
//回溯逻辑处理
target += i;
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
}
};
代码
class Solution {
private:
vector<int> path;
vector<vector<int>> res;
//确定递归函数的参数和返回值
void backtracking(int k, int target, int beginIndex){
//终止条件
if(path.size() == k){//是否遍历到叶子节点
if(target == 0){//若target为0，则当前path中保存的路径值之和满足为n的条件
res.push_back(path);
return;
}
}
//确定单层处理逻辑
for(int i = beginIndex; i <= 9; ++i){
target -= i;//当前路径值与target作差
path.push_back(i);//保存当前路径值
backtracking(k, target, i + 1);//触发下层递归，跳过当前值
//回溯逻辑处理
target += i;
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
backtracking(k, n, 1);
return res;
}
};