回溯 <---->递归
1.递归的下面就是回溯的过程
2.回溯法是一个 纯暴力的 搜索
3.回溯法解决的问题：
3.1组合 如：1234 两两组合 3.2切割问题 如：一个字符串有多少个切割方式 ，或者切割出来是回文 3.3子集 ： 1 2 3 4 的子集 3.4排列问题（顺序） 3.5棋盘问题：n皇后 解数独
4.回溯可抽象成树形结构
树的宽度是集合的数目 for循环
树的深度是递归的层数
5.void backtracking(){
进入终止条件后开始
if(终止条件) {
收集结果 return //本层函数调用结束 }
for(集合的元素集，类似子节点的个数)
{
处理结点
递归函数；
回溯操作
（撤销处理结点12， 2撤销 ，13 撤销3， 14）
}
return
}
组合问题1 2 3 4
比如求两个数的组合 12 13 14 23 24 34 可以两层for循环
如果10个数求三个数的组合 三层for循环
n个数求50个数的组合 50层for循环 不合理
所以 用回溯（递归）来控制for循环的次数
树形结构
可以看出这个棵树，一开始集合是 1，2，3，4， 从左向右取数，取过的数，不在重复取。
第一次取1，集合变为2，3，4 ，因为k为2，我们只需要再取一个数就可以了，分别取2，3，4，得到集合[1,2] [1,3] [1,4]，以此类推。
回溯三部曲-
递归函数参数和返回值
-
确定终止条件
-
单层递归逻辑
-
递归函数参数和返回值
参数 二维数组result 存放最后结果
一维数组path 存放路径上的值
n个数 k个数的组合 startindex 告诉递归每层从哪个数开始取 比如在第二层中从234开始取 -
确定终止条件
叶子节点 结果的大小是2 path.size==k 收集path结果 -
单层递归逻辑
先将节点i加入路径path
回溯（因为要进入下一层 开始的结点是从i+1开始）
撤回结点 path.pop()
private:
vector> result; // 存放符合条件结果的集合
vector path; // 用来存放符合条件结果
void backtracking(int n, int k, int startIndex) {
if (path.size() == k) {
result.push_back(path);//取一条路径上的结果
return;
}
for (int i = startIndex; i <= n; i++) {
path.push_back(i); // 处理节点
backtracking(n, k, i + 1); // 递归
path.pop_back(); // 回溯，撤销处理的节点
}
}
public:
vector> combine(int n, int k) {
result.clear(); // 可以不写
path.clear(); // 可以不写
backtracking(n, k, 1);
return result;
}
};
组合问题剪枝
来举一个例子，n = 4，k = 4的话，那么第一层for循环的时候，从元素2开始的遍历都没有意义了（因为只剩下3,4达不到4个数字）。在第二层for循环，从元素3开始的遍历都没有意义了。
即 每一层的for循环从第二个数开始遍历的话，都没有意义。
「所以，可以剪枝的地方就在递归中每一层的for循环所选择的起始位置」。
「如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了」。
注意代码中i，就是for循环里选择的起始位置。
for (int i = startIndex; i <= n; i++) {
接下来看一下优化过程如下：
- 已经选择的元素个数：path.size();
- 还需要的元素个数为: k - path.size();
- 在集合n中至少要从该起始位置 : n - (k - path.size()) + 1，开始遍历
就是说从开始位置到最终位置还需要 k - path.size()个元素
所以设开始位置为index 所以n-index+1= k - path.size() 所以index= n - (k - path.size()) + 1
举个例子，n = 4，k = 3， 目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。从2开始搜索都是合理的，可以是组合[2, 3, 4]。
所以优化之后的for循环是：
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置
class Solution {
private:
vector> result;
vector path;
void backtracking(int n, int k, int startIndex) {
if (path.size() == k) {
result.push_back(path);
return;
}
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) { // 优化的地方 就是结点孩子的个数
path.push_back(i); // 处理节点
backtracking(n, k, i + 1);//递归就是沿着树枝往下搜索的过程
path.pop_back(); // 回溯，撤销处理的节点
}
}
public:
vector> combine(int n, int k) {
backtracking(n, k, 1);
return result;
}
};
组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1： 输入：candidates = [2,3,6,7], target = 7, 所求解集为： [ [7], [2,2,3] ]
示例 2： 输入：candidates = [2,3,5], target = 8, 所求解集为： [ [2,2,2,2], [2,3,3], [3,5] ]
#思路
回溯三部曲
- 函数参数和返回值
路径上的值的组合如[1,2]为path 一维数组
result 二维数组，将符合的path放入result中
s为path内所有元素的和
target 目标和
startindex 开始的搜索的结点
candidate 集合
- 终止条件
if( s>target) //return
if( s==target)
result.push_back(path)//收集结果
return
- 单层搜索逻辑
for (int i = startIndex; i < candidates.size(); i++) {集合的长度
sum += candidates[i];
path.push_back(candidates[i]);
backtracking(candidates, target, sum, i); // 关键点:不用i+1了，表示可以重复读取当前的数
sum -= candidates[i]; // 回溯
path.pop_back(); // 回溯
}
// 版本一
class Solution {
private:
vector> result;
vector path;
void backtracking(vector& candidates, int target, int sum, int startIndex) {
if (sum > target) {
return;
}
if (sum == target) {
result.push_back(path);
return;
}
for (int i = startIndex; i < candidates.size(); i++) {
sum += candidates[i];
path.push_back(candidates[i]);
backtracking(candidates, target, sum, i); // 不用i+1了，表示可以重复读取当前的数
sum -= candidates[i];
path.pop_back();
}
}
public:
vector> combinationSum(vector& candidates, int target) {
result.clear();
path.clear();
backtracking(candidates, target, 0, 0);
return result;
}
};
状态空间树
蒙特卡罗 找到一定范围的解 一定能在这个范围内找到解
拉斯维加斯 找到精确的解 但是解不一定正确
因为每个背包都有选还是不选两种选择
n皇后 不同行不同列 不在同一对角线
xi表示的是列号
判断k行皇后是否可以放在i列上面
相邻的图连起来就可以
