- 回溯法也可以叫做回溯搜索法，它是一种搜索的方式。
- 回溯是递归的副产品，只要有递归就会有回溯。
虽然回溯法不好理解，但是回溯法并不是什么高效的算法。
因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝操作，但也改不了回溯法就是穷举的本质。
既然回溯法并不高效为什么还要用它呢？因为没得选，有些问题只能暴力搜出来，最多再剪枝一下，并没有更高效的解法。
回溯法，一般可以解决如下几种问题：
- 组合问题：N 个数里面按一定规则找出 k 个数的集合
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个 N 个数的集合里有多少符合条件的子集
- 排列问题：N 个数按一定规则全排列，有几种排列方式
- 棋盘问题：N 皇后，解数独等等
所有回溯法解决的问题都可以抽象为树形结构。
因为回溯法解决的都是在集合中递归查找子集，**集合的大小构成了树的宽度，递归的深度构成树的深度。
递归就要有终止条件，所以必然是一棵高度有限的树（N 叉树）。
- 回溯算法中函数返回值一般为
void - 因为回溯算法需要的参数不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。
回溯函数伪代码如下：
void backtracking(参数)一般来说搜到叶子节点了，也就找到满足条件的一条答案，把这个答案存放起来，并结束本层递归。
所以回溯函数终止条件伪代码如下：
if (终止条件) {
存放结果;
return;
}回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。
回溯函数遍历过程伪代码如下：
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}for 循环就是遍历集合区间，可以理解一个结点有多少个孩子，这个 for 循环就执行多少次。
for 循环可以理解是横向遍历，backtracking 就是纵向遍历，这样就把这棵树遍历完了，一般来说，搜索叶子节点就是找到其中一个结果。
分析完整个过程，回溯算法模板框架如下：
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}-
时间复杂度：$O(n × 2^n)$，每一个元素的状态为取与不取，所以时间复杂度为
$O(2^n)$ ，构造每一组子集都需要填进数组，又有需要$O(n)$ ，最终时间复杂度：$O(n × 2^n)$。 -
空间复杂度：$O(n)$，递归深度为
n，所以系统栈所用空间为$O(n)$ ，每一层递归所用的空间都是常数级别。 代码里的result和path都是全局变量，就算是放在参数里，传的也是引用，并不会新申请内存空间，最终空间复杂度为$O(n)$ 。
-
时间复杂度：$O(n!)$，这个可以从排列的树形图中看出，第一层节点为
n，第二层每一个分支都延伸了n-1个分支，再往下是n-2个分支，所以一直到叶子节点一共就是n * n-1 * n-2 * ... * 1 = n!。 每个叶子结点都会有一个构造全排列填进数组的操作，该操作的复杂度为$O(n)$ 。 所以，最终时间复杂度为：n * n!，简化为$O(n!)$ 。 - 空间复杂度：$O(n)$，和子集问题同理。
- 时间复杂度：$O(n × 2^n)$，组合问题其实就是一种子集的问题，所以组合问题最坏的情况，也不会超过子集问题的时间复杂度。
- 空间复杂度：$O(n)$，和子集问题同理。
一般说道回溯算法的复杂度，都说是指数级别的时间复杂度。
-
时间复杂度：$O(n!)$，直觉上是
$O(n^n)$ ，但皇后之间不能见面所以在搜索的过程中是有剪枝的，最差也就是 $O(n!)。 - 空间复杂度：$O(n)$，和子集问题同理。
-
时间复杂度：$O(9^m)$，
m是'.'的数目。 -
空间复杂度：$O(n^2)$，递归的深度是
$n^2$