LeetCode-回溯
回溯 -》 穷举
- 回溯函数模板返回值以及参数
- 回溯函数终止条件
- 回溯搜索的遍历过程
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
1. 组合 1\. 组合
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
思路： 数字中有多少中组合，k为2的话，两个for可以解决，k为为100 就不能这么做了
首先 ：
- 回溯函数的模版是怎样的
不需要返回值，参数需要 知道哪里开始，哪里结束，截止需要的条件
- 终止条件
回溯拿到k个数的时候即停止
- 就改题而言过程是要遍历每个数，即一for循环加上回溯函数
class Solution {
public:
vector<vector<int>> res; //最终结果保存的地方
vector<int> path; //每一轮回溯结果保存的地方
void back(int n,int k,int index){ //n 哪里结束，k 截止需要的条件，index 其实的地方
if(path.size() == k){ //当path 满足 k 个时候就可以保存到 res中
res.push_back(path);
return;
}
for(int i = index; i <= n ;i++){ // 遍历每个数 每个数都可能做为第一个数
path.push_back(i); //保存
back(n,k,i+1); // i+1 意思是下一轮从下一个数开始
path.pop_back(); //满足条件了，就出栈，腾出空间给下个数
}
}
vector<vector<int>> combine(int n, int k) {
back(n,k,1); //
return res;
}
};
2. 组合总和 III 2\. 组合总和 III
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
- 和上题差不多，1到9的数字总，k个组合的数之和为n
还是来三部曲：
- 回溯函数的参数
back(int target,int k,int index,int sum) //k 为组合个数，target 组合之和，index 起始的地方，sum 记录总和
- 终止条件
组合个数位k，并且呢 组合之和为 target
- 搜索过程
还是遍历，就是遍历计数时 还要记录总和sum
class Solution {
public:
vector<vector<int>> res; //最终结果保存的地方
vector<int> path; //每一轮回溯结果保存的地方
void back(int target,int k,int index,int sum){
if(path.size() == k){ //当path 满足 k 个时，sum 等于 target
if(sum == target)
res.push_back(path);
return;
}
for(int i = index; i <= 9 ;i++){ // 遍历每个数 每个数都可能做为第一个数
path.push_back(i); //保存
sum = sum + i; //这里计算总和
back(target,k,i+1,sum);
path.pop_back(); //出栈了，总和也要
sum = sum -i;
}
}
vector<vector<int>> combinationSum3(int k, int n) {
int sum = 0;
back(n,k,1,sum);
return res;
}
};