什么是回溯算法

回溯法也称回溯搜索法，它是一种搜索的方式。在递归中我们常听到回溯这个操作，其实回溯就是递归中的一个子过程，只要有递归就会有回溯。回溯法并不是什么高效的算法，而是对于一些暴力算法都无法解决的问题，就必须使用回溯法对所有可能的结果进行穷举。因此，回溯算法本身的效率是不高的，顶多使用剪枝对其一些不必要的子过程进行修剪。

回溯算法能够解决的问题

一般来说，主要使用回溯算法解决如下几类问题：

1. 组合问题：N个元素中按一定规则找出K个元素的集合（不考虑顺序）
2. 切割问题：一个字符串按一定规则有多少种切割的方式
3. 子集问题：一个N个元素的集合有多少符合条件的子集（不考虑顺序）
4. 排列问题：N个元素按一定规则全排列，有几种排列方式（考虑顺序）
5. 棋盘问题：N皇后，解数独等等 由此可知，回溯法解决的问题都可以抽象为树形结构。因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。而递归就要有终止条件，所以必然是⼀棵高度有限的树（N叉树）。

回溯算法模板

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

void back_tracking(参数) {
    if (终⽌条件) {
        存放结果;
        return;
    }
    for (选择：本层集合中元素（树中节点孩⼦的数量就是集合的⼤⼩）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

在回溯算法中一般包含两个主要模块，首先是当回溯算法搜索到叶子结点时，就找到了满足条件的一个答案，需要把这个答案存放起来结束本层递归。其次，在前文中提到集合的大小决定了树的宽度。因此for循环就是在遍历当前集合中有多少个子集合（子结点）。后面将结合具体题目对以上模板进行详细解释。