Backtracking Algorithm - tenji/ks GitHub Wiki
回溯算法
一、概念
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
许多复杂的，规模较大的问题都可以使用回溯法，有通用解题方法的美称。
注意：由于回溯法花费时间较长，所以对于没有明确的动态规划（DP）和递归解法的或问题要求满足某种性质（约束条件）的所有解或最优解时，才考虑使用回溯法。
回溯算法适用于以下问题：
- 排列
- 组合
- 切割
- 子集
- 棋盘
提示：当遇到需要多重循环，但是循环层次不确定的问题时，就需要联想到回溯算法了。
二、与 DFS 的区别
DFS 和回溯法其主要的区别是：回溯法在求解过程中不保留完整的树结构，而深度优先搜索则记下完整的搜索树。
简化理解：回溯算法 = 树的深度优先搜索 + 剪枝函数
什么是剪枝函数？
为了提高搜索效率，在搜索过程中使用约束函数，可以避免无谓地搜索那些已知不含答案状态的子树。如果是最优化问题，还可以使用限界函数剪去那些不可能含有最优解的子树。约束函数和限界函数目的相同，都是为了剪去不必要搜索的子树，减少问题求解所需实际生成的状态结点数，他们统称为剪枝函数。
三、回溯流程
- 针对所给问题，确定问题的解空间：首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解；
- 确定结点的扩展搜索规则；
- 以深度优先搜索方式搜索空间，并在搜索过程中用剪枝函数避免无效搜索。
四、伪代码模板
抽象地说，解决一个回溯问题，实际上就是遍历一棵决策树的过程，树的每个叶子节点存放着一个合法答案。你把整棵树遍历一遍，把叶子节点上的答案都收集起来，就能得到所有的合法答案。
站在回溯树的一个节点上，你只需要思考 3 个问题：
- 路径：也就是已经做出的选择。
- 选择列表：也就是你当前可以做的选择。
- 结束条件：也就是到达决策树底层，无法再做选择的条件。
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
五、分析样例
5.1 题目描述
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例1：
输入：n = 4
输出：[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."](/tenji/ks/wiki/".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q..")
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例2：
输入：n = 1
输出：["Q"](/tenji/ks/wiki/"Q")
提示：
1 <= n <= 9
5.2 题目分析
以 4 皇后问题为例，递归树如下：
