👉回溯算法👈
什么是回溯法
- 回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就回溯返回，尝试别的路径。
- 回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为回溯点。也可以称为剪枝点，所谓的剪枝，指的是把不会找到目标，或者不必要的路径裁剪掉。
许多复杂的，规模较大的问题都可以使用回溯法，有通用解题方法的美称。回溯法主要解决的问题如下图：
注：组合是不强调元素顺序的，而排列是强调元素顺序的。比如：{1, 2} 和 {2, 1} 在组合上，就是一个集合，因为不强调顺序，而要是排列的话，{1, 2} 和 {2, 1} 就是两个集合了。记住组合无序，排列有序，就可以了。
回溯法解决的问题都可以抽象为树形结构，因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。
在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解。如果包含，就从该结点出发继续探索下去；如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。
若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。
而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。
除了深度优先搜索，常用的还有广度优先搜索。
回溯算法的模板
- 回溯函数模板的返回值和参数
在回溯算法中，函数的名字一般是 BackTracking（原路返回）、DFS（深度优先遍历）或 BFS（广度优先遍历）。函数名字根据自己的习惯去，最好是顾名思义的。回溯算法的返回值一般是 void，参数一般是输出型参数。输出型参数在递归搜索的过程中，收集符合要求的结果，参数的多少一般取决于题目。
回溯函数的终止条件
回溯法解决的问题都可以抽象成树形结构，遍历树形结构是需要终止条件的。那回溯函数的终止条件是什么呢？树形结构的遍历是需要遍历到叶子节点，到了叶子节点就找到了符合要求的一个解了，然后就可以结束本层的递归。注：此处所指的叶子节点是符合题目要求的节点。遍历时也会遇到不符合结果的叶子节点，此这时候就需要回溯了，不再往下进行搜索。
回溯搜索的遍历过程
在上面我们提到了，回溯一般是在集合中搜索。集合的元素个数就构成了树的宽度，递归的深度就构成了树的深度。如下图所示：
注：for 循环可以理解是横向遍历，backtracking（递归）就是纵向遍历。
回溯算法模板伪代码
void backtracking(参数) { if (终止条件) { 收集结果; return; } for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小)) { 处理节点; backtracking(路径，选择列表); // 递归 回溯，撤销处理结果 } }
这份模板很重要，后面做回溯算法的题目就靠它了。
👉组合👈
组合问题是用回溯算法解决的经典题目。因为用回溯算法解决的问题都可以抽象为属性结构，那么我们就可以将组合问题抽象成下图的样子。
可以看出这棵树，一开始集合是 1，2，3，4， 从左向右取数，取过的数，不再重复取。第一次取1，集合变为2，3，4 。因为 k 为 2，我们只需要再取一个数就可以了，分别取2，3，4，得到集合 [1,2] [1,3] [1,4]，以此类推。我们可以发现：n 就是树的宽度，k 就是递归的深度。
递归函数的参数：在这里，我们可以在类里声明两个私有变量来存储结果，分别是vector<vector<int>> result 和vector<int> path。result 是用来存放符合条件结果的集合，而 path 是用来存放符合条件。函数里一定有两个参数，既然是集合 n 里面取 k 个数，那么 n 和 k 是两个 int 型的参数。为了防止出现重复的组合，还需要一个参数 startIndex 来记录下一层递归搜索的起始位置。
递归的终止条件：在前面我们提及到，到了叶子节点就可以收集结果了。那什么时候到达所谓的叶子结点呢？通过下图，我们可以发现：当 path 数组的元素个数到达了 k，就说明我们找到了子集大小为 k 的集合了，就可以收集结果了。注：path 是从根节点到叶子节点的路径。
单层的遍历搜索过程：回溯法的搜索过程就是树形结构的变量过程，for 循环用来横向遍历，递归用来纵向遍历。for 循环每次从 startIndex 开始，然后用 path 数组保存节点 i。
完整代码
class Solution { private: vector<vector<int>> result; vector<int> path; void BackTracking(int n, int k, int startIndex) { if(path.size() == k) { // 收集结果 result.push_back(path); return; } // 横向遍历 for(size_t i = startIndex; i <= n; ++i) { path.push_back(i); // 处理节点 BackTracking(n, k, i + 1); // 递归 path.pop_back(); // 回溯 } } public: vector<vector<int>> combine(int n, int k) { result.clear(); // 防止用同一个对象重复调用该函数,可以不做 path.clear(); // 防止用同一个对象重复调用该函数,可以不做 BackTracking(n, k, 1); return result; } };
剪枝优化
我们知道，回溯是暴力搜索的过程，其实这个搜索的过程也是可以通过剪枝来优化一下的。
在横向遍历的过程中有如下代码：
for (int i = startIndex; i <= n; i++) { path.push_back(i); BackTracking(n, k, i + 1); path.pop_back(); }
这个遍历的范围是可以剪枝优化的，那怎么优化呢？来举一个例子，n = 4，k = 4 的话，那么第一层 for 循环的时候，从元素 2 开始的遍历都没有意义了。 在第二层 for 循环，从元素 3 开始的遍历都没有意义了。
该题的剪枝优化是：如果 for 循环选择的起始位置之后的元素个数已经不足我们需要的元素个数了，那么就没有必要搜索了。 我们知道path.size()是已经选择的元素个数，k - path.size()是还需要的元素个数。for 循环是从 startIndex 开始的，也就是说从 startIndex 到循环的上界能够凑出k - path.size()个元素就能够得到符合要求的结果。如果不能凑出，就无法得到符合要求的结果，无需再遍历。那么现在我们就来求一下循环的上界是多少，求解过程如下图：
那么经过剪枝优化后，代码就变成下面的样子了。
class Solution { private: vector<vector<int>> result; vector<int> path; void BackTracking(int n, int k, int startIndex) { if(path.size() == k) { // 收集结果 result.push_back(path); return; } // 横向遍历 // 剪枝优化 for(size_t i = startIndex; i <= n + 1 - (k - path.size()); ++i) { path.push_back(i); // 处理节点 BackTracking(n, k, i + 1); // 递归 path.pop_back(); // 回溯 } } public: vector<vector<int>> combine(int n, int k) { result.clear(); // 防止用同一个对象重复调用该函数,可以不做 path.clear(); // 防止用同一个对象重复调用该函数,可以不做 BackTracking(n, k, 1); return result; } };
