回溯

回溯法也叫回溯搜索法，它是一种搜索的方式

只要有递归就会有回溯

回溯法的工作原理

• 构造空间树

• 进行遍历

• 如遇到边界条件，即不再向下搜索，转而搜索另一棵子树

• 达到目标条件，输出结果

回溯的本质是穷举，即便加入 剪枝 操作，回溯法也并不高效

回溯法一般可以解决如下几种问题：

• 组合问题 ：N 个数里面按一定规则找出 k 个数的集合
• 切割问题 ：一个字符串按一定规则有几种切割方式
• 子集问题 ：一个 N 个数的集合里有多少符合条件的子集
• 排列问题 ：N 个数按一定规则全排列，有几种排列方式
• 棋盘问题 ：N 皇后，解数独等等

以上问题都可以近似成：在集合中查找子集。可以把这些问题抽象为树形结构，集合大小决定了树的宽度，递归的深度（例如，子集的大小）决定了树的深度

回溯法的算法框架如下：（回溯函数，也就是递归函数）

1. 回溯函数模板返回值以及参数

   • 回溯算法中函数返回值一般为 void
   • 回溯算法需要的参数并不像二叉树递归那样容易确定，一般是先写逻辑，然后再看需要什么参数

2. 回溯函数终止条件：回溯法解决的问题都可以抽象成树形结构，因此，一般来说，遇到叶节点也就说明找到了一个符合条件的答案，记录答案，然后结束本层递归

3. 回溯搜索的遍历过程：

   • for 循环用于实现横向遍历（在同一层遍历不同的节点）
   • 递归用于实现纵向遍历（遍历不同的层次）

回溯算法模板：

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

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