前言
回溯第二篇。
回顾：上一篇学了回溯的基础知识和模版；组合练习题一应用了一次模版。
本文继续组合问题练习：记录 六十四【216.组合总和III】。
一、题目阅读
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
- 只使用数字1到9
- 每个数字 最多使用一次
- 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。
示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。
示例 3:
输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。
提示:
2 <= k <= 9
1 <= n <= 60
二、尝试实现
思路【不剪枝】
- 题目分析：使用数字范围[1,9]，每个数字只能用一次。找一个组合，元素个数是k，求和是n。组合问题：回溯思路。
- 利用回溯模版开始写递归函数：
- 递归函数返回值：用vector< int>& temp和vector<vector< int>>& result搜集结果，放到参数里面，无需返回值。所以是void。
- 递归函数参数：
- int k,int n ,vector< int>& temp和vector<vector< int>>& result已经有4个了；
- int startindex用来确定每一层for循环的开始元素；
- int& sum搜集结果时要判断这个组合之和是否为n，所以用sum来记录。很明显，sum跟随temp回溯。
- 递归函数终止条件：深度是k，所以temp.size() == k条件一；如果sum==n，那么放入result后return；如果sum!= n，直接return。
- 递归函数单层逻辑：
- for循环：每一层有几种可能。所以起始元素startindex传入，终止以9结尾。（不剪枝，暴力搜索每一个组合）；
- for循环内部：先放入本层元素；再sum加上放入的元素；递到下一层；回溯temp和sum。（四步）
代码实现
class Solution {
public:
void backtracking(int k,int n,int startindex,int& sum,vector<int>& temp,vector<vector<int>>& result){
//终止条件
if(temp.size() == k && sum != n){//当个数满足但是和不相等时，直接return。
return;
}
if(temp.size() == k&& sum == n){//当个数满足且和相等时，放入最终结果集，再return。
result.push_back(temp);
return;
}
for(int i = startindex;i <= 9;i++){
temp.push_back(i);//放入本层元素。
sum += i;//求和
backtracking(k,n,i+1,sum,temp,result);//递到下一层
temp.pop_back();//回溯操作。
sum -= i;
}
return;
}
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> result;
vector<int> temp;//放中间结果
int sum = 0;
backtracking(k,n,1,sum,temp,result);
return result;
}
};
思路【剪枝】
肯定从和入手，本层剩余加入元素个数：k-temp.size()；剩余和：n-sum。
之后……
三、参考学习
学习内容
- 不剪枝的思路和实现就是二、尝试实现；
- 如何剪枝？
- 如果sum已经大于n，此时temp.size()还没有等于k，可以直接return，无需进入for循环取值；
- 要求k个元素，如果选某个元素后，剩余子集大小不足k个，那么这个元素也不能选。所以i <= 9换成i <= 9-(k-temp.size())+1.
- 代码实现【剪枝】：
class Solution {
public:
void backtracking(int k,int n,int startindex,int& sum,vector<int>& temp,vector<vector<int>>& result){
//终止条件
if(sum > n) return;//剪枝一；
if(temp.size() == k && sum != n){//当个数满足但是和不相等时，直接return。
return;
}
if(temp.size() == k&& sum == n){//当个数满足且和相等时，放入最终结果集，再return。
result.push_back(temp);
return;
}
for(int i = startindex;i <= 9-(k-temp.size())+1;i++){//剪枝二；
temp.push_back(i);//放入本层元素。
sum += i;//求和
backtracking(k,n,i+1,sum,temp,result);//递到下一层
temp.pop_back();//回溯操作。
sum -= i;
}
return;
}
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> result;
vector<int> temp;//放中间结果
int sum = 0;
backtracking(k,n,1,sum,temp,result);
return result;
}
};
总结
本文和记录 六十三【回溯章节开篇】的知识点相同，使用回溯模版。
（欢迎指正，转载标明出处）
标签：216,return,temp,int,sum,力扣,vector,result,III From： https://blog.csdn.net/danaaaa/article/details/140902034