【算法】回溯法Backtracking

回溯法即回溯搜索法Backtracking（回溯算法和DFS都属于搜索问题的解的方法，任何解空间可以映射成树结构的问题，都可以使用回溯法！！！回溯法=DFS+剪枝）

回溯算法本质是穷举搜索！！！回溯算法建立在 DFS 基础之上的，回溯法以深度优先搜索的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。。比如当前局面下，我们有若干种选择，所以我们对每一种选择进行尝试。如果发现某种选择违反了某些限定条件，此时 return到上一层（也叫回溯）；如果尝试某种选择到了最后，发现该选择是正确解，那么就将其加入到解集中。回溯需要不断调用自身函数(运用到递归结构)，但这里的调用自身函数不是和递归一样去解决子问题，而是为了穷举所有可能的情况。

“上图的找到答案后尝试别的可能” 的意思可以参考力扣22题括号生成来理解，因为有时候所有有效的答案都需要被返回，不止一个。

解题方法：首先一定要画图，按照递归的画法（因为回溯法属于递归）把所有的可能先穷举列出来，这里并不用考虑是否有效（这里以力扣22题括号生成举例，当n=2时，括号的所有的排列组合如下图所示，这里穷举时不考虑括号是有效还是没效）。

穷举完所有的排列组合后，然后把有效的定义抽象出来，从上图可以发现，在遍历过程中，一旦右边的括号大于左边的括号的数量时就不是有效的。一旦无效，就没要必要再往下走了。

模板

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13

refer：
回溯算法以及其模板