回溯(Backtracking)是指在求解的过程中，不断的试探每一步的所有可能的解，如果发现不符合要求，就回退到最初的状态，尝试另外一种可能，直到所有的可能的解都找到。它与DFS的思想是一致的。

回溯通常用来解决的问题是，问题会分成很多步骤，每一步面临多个选择，有多种可能性，需要一个一个的尝试，最终需要找到所有的可能的解。回溯通常用递归来实现，并且它的时间复杂度一般都比较高。它基本上就是穷举和暴力搜索一样，但通过各种奇技淫巧可以做剪枝以降低复杂度。

最为经典的回溯算法问题就是迷宫问题，比如从一个格子a，出发，有二个方向，还不知道哪个是对的，那就分别向前走，一直走，直到撞墙了，或者到了死路了，才知道这个方向是错的；然后回退到a，按个方向继续走，这就是经典的回溯。

回溯的模板套路

运用回溯算法需要厘清四个条件：1）把问题每成多个步骤，一步一步的走完，就得到了一个解；2）每个步骤又分成多个备选选择，有些是符合要求的，有些则是不符合要求的；3）什么条件算是得到了解，或者说什么情况下算是把问题解决了，在这个条件时终止递归，并得到一个解；4）剪枝，如何剪掉不符合题意的选择或者步骤。

虽然说具体的问题的分析场景不太一样，也就是说具体的每个问题的分为子问题的方式，以及子问题的解决步骤还有回溯方式是不一样的，但整体来说，回溯算法是有套路的：

1
2
3
4
5
6
7
8

def backtracking(current_option):
   if satisfied:
     return solution
   if not satisfied:
     return null
   next_option = getNext()
   backtrack(next_option)
   undo next_option

下面来看一下一些典型的可以用回溯算法来求解的问题类型。

递归树

回溯是一个DFS的过程，是在遍历一颗递归树(State space tree)，所以要想更好的应用回溯，最好画出一颗递归树，以更好的厘清回溯过程和剪枝。一个节点代表一个状态，一个路径代表一个操作，叶子节点表示递归到达终止条件。 比如说子集问题，给定一个无重复元素的数组，找出所有的子集，比如给定[1,2,3]，那么递归树就会是这个样子的:

剪枝即是依据某些约束条件，把不符合要求的路径排除在外，这不单单排除一个节点，而是把这个节点的所在的路径都排除了，这个节点及其后面的DFS都不需要做了，就像把树的一根分杈剪掉一样，所以形象的称之为剪枝。

基础回溯问题

有一些非常典型的用回溯解决的问题，如子集（幂集），组合和排列问题，这些问题是基础的回溯算法应用问题，有标准的套路，用于理解回溯和训练加溯思维都是很好的例子。

子集(幂集)问题

子集是指一个如果 一个集合A的元素都属于另一个集合B，那么A就是B的一个子集，空集和全集也都是子集。回溯算法解决的问题，更准确的说是求一个给定集合（一般以数组形式给出）的幂集。一个集合所有子集所组成的集合，称之为该集合的幂集(Power set)。集合中每一个元素都有两种选择，加入某个子集，或者不加入，假如集合大小为n，那么一共会有2ⁿ个不同的子集，所以子集相关问题的复杂度，至少会是O(2ⁿ)的。

组合问题

排列问题

高级回溯问题（搜索问题）

棋盘类问题

分割类问题

构造类问题

DFS+回溯

其他枚举类问题

回溯本质上就是暴力穷举，所以一些枚举类问题也可以通过回溯来解决。

参考资料

• Introduction to Backtracking
• Backtracking Algorithm Explained With Examples
• Backtracking Algorithm
• What is Backtracking Algorithm? Types, Examples & its Application
• Backtracking Algorithms Explained
• Leetcode 刷题笔记(二十) ——回溯算法篇之分割、子集、全排列问题
• 回溯算法详解
• 回溯算法详细总结
• [回溯算法] 五大常用算法之回溯法
• 小白带你学–回溯算法
• 回溯算法套路详解
• 关于回溯算法，你该了解这些！
• 彻底搞懂回溯算法（本文真的很详细）
• 【算法】回溯
• 理解回溯算法——回溯算法的初学者指南
• 一文带你了解回溯算法的套路
• C++ 总结了回溯问题类型 带你搞懂回溯算法(大量例题)
• 回溯算法入门级详解 + 练习（持续更新）