回溯算法框架
解决一个回溯问题，实际上就是一个决策树的遍历过程。你只需要思考 3 个问题：
- 路径：也就是已经做出的选择。
- 选择列表：也就是你当前可以做的选择。
- 结束条件：也就是到达决策树底层，无法再做选择的条件。
如果你不理解这三个词语的解释，没关系，我们后面会用「全排列」和「N 皇后问题」这两个经典的回溯算法问题来帮你理解这些词语是什么意思，现在你先留着印象。
回溯算法的代码框架：
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」。
什么叫做选择和撤销选择呢，这个框架的底层原理是什么呢？下面我们就通过「全排列」这个问题来解开之前的疑惑，详细探究一下其中的奥妙！
全排列
为了简单清晰起见，我们这次讨论的全排列问题不包含重复的数字。
那么我们怎么穷举全排列的呢？比方说给三个数 [1,2,3]，你肯定不会无规律地乱穷举，一般是这样：
先固定第一位为 1，然后第二位可以是 2，那么第三位只能是 3；然后可以把第二位变成 3，第三位就只能是 2 了；然后就只能变化第一位，变成 2，然后再穷举后两位……
其实这就是回溯算法，其回溯树如下：
只要从根遍历这棵树，记录路径上的数字，其实就是所有的全排列。我们不妨把这棵树称为回溯算法的「决策树」。
为啥说这是决策树呢，因为你在每个节点上其实都在做决策。比如说你站在下图的红色节点上：
你现在就在做决策，可以选择 1 那条树枝，也可以选择 3 那条树枝。为啥只能在 1 和 3 之中选择呢？因为 2 这个树枝在你身后，这个选择你之前做过了，而全排列是不允许重复使用数字的。
现在可以解答开头的几个名词：[2] 就是「路径」，记录你已经做过的选择；[1,3] 就是「选择列表」，表示你当前可以做出的选择；「结束条件」就是遍历到树的底层，在这里就是选择列表为空的时候。
如果明白了这几个名词，可以把「路径」和「选择」列表作为决策树上每个节点的属性，比如下图列出了几个节点的属性：
我们定义的 backtrack 函数其实就像一个指针，在这棵树上游走，同时要正确维护每个节点的属性，每当走到树的底层，其「路径」就是一个全排列。
现在，你是否理解了回溯算法的这段核心框架？
for 选择 in 选择列表:
# 做选择
将该选择从选择列表移除
路径.add(选择)
backtrack(路径, 选择列表)
# 撤销选择
路径.remove(选择)
将该选择再加入选择列表
我们只要在递归之前做出选择，在递归之后撤销刚才的选择，就能正确得到每个节点的选择列表和路径。
show code
List<List<Integer>> res = new LinkedList<>();
/* 主函数，输入一组不重复的数字，返回它们的全排列 */
List<List<Integer>> permute(int[] nums) {
// 记录「路径」
LinkedList<Integer> track = new LinkedList<>();
backtrack(nums, track);
return res;
}
// 路径：记录在 track 中
// 选择列表：nums 中不存在于 track 的那些元素
// 结束条件：nums 中的元素全都在 track 中出现
void backtrack(int[] nums, LinkedList<Integer> track) {
// 触发结束条件
if (track.size() == nums.length) {
res.add(new LinkedList(track));
return;
}
for (int i = 0; i < nums.length; i++) {
// 排除不合法的选择
if (track.contains(nums[i]))
continue;
// 做选择
track.add(nums[i]);
// 进入下一层决策树
backtrack(nums, track);
// 取消选择
track.removeLast();
}
}
回溯算法不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高。
N皇后
这个问题很经典了，简单解释一下：给你一个 N×N 的棋盘，让你放置 N 个皇后，使得它们不能互相攻击。
注意：皇后可以攻击同一行、同一列、左上左下右上右下四个方向的任意单位。
这个问题本质上跟全排列问题差不多，决策树的每一层表示棋盘上的每一行；每个节点可以做出的选择是，在该行的任意一列放置一个皇后。
show code
/**
* 八皇后问题：8x8 的棋盘，希望往里放 8 个棋子（皇后），每个棋子所在的行、列、对角线都不能有另一个棋子
*
* @author Mr.Huang at 2020-05-31 15:29
**/
public class QueenSettle {
private static Integer N = 8;
/**
* @param selectedColumns 已选解集合,下标表示行,值表示queen存储在哪一列
* @param row 可选的空间解,第 n 行可选
*/
public static void queenSettle(int[] selectedColumns, int row) {
// 终止条件
if (row > N - 1) {
// 说明前 N 行都已经都选完皇后了，
printQueens(selectedColumns);
return;
}
for (int i = 0; i < N; i++) {
// 剔除不合法的格子
if (!isValid(row, i, selectedColumns)) {
continue;
}
// 选择子节点（当前行）其中一个解
selectedColumns[row] = i;
// 选完之后再进入下个阶段的（下一行）遍历
queenSettle(selectedColumns, row + 1);
// 回溯,换一个解继续 dfs，回溯时要把回溯节点的解移除
selectedColumns[row] = -1;
}
}
/**
* 判断相应的格子放置皇后是否OK
*
* @param row
* @param column
* @param selectedColumns
* @return
*/
private static boolean isValid(int row, int column, int[] selectedColumns) {
//判断row行column列放置是否合适
int leftup = column - 1, rightup = column + 1;
// 逐行往上考察每一行
for (int i = row - 1; i >= 0; --i) {
// 第i行的column列有棋子吗？
if (selectedColumns[i] == column) {
return false;
}
// 考察左上对角线：第i行leftup列有棋子吗？
if (leftup >= 0) {
if (selectedColumns[i] == leftup) {
return false;
}
}
// 考察右上对角线：第i行rightup列有棋子吗？
if (rightup < 8) {
if (selectedColumns[i] == rightup) {
return false;
}
}
--leftup;
++rightup;
}
return true;
}
public static void main(String[] args) {
int[] selectedColumn = new int[N];
// 从第 0 行开始 DFS
queenSettle(selectedColumn, 0);
}
private static void printQueens(int[] result) { // 打印出一个二维矩阵
for (int row = 0; row < 8; ++row) {
for (int column = 0; column < 8; ++column) {
if (result[row] == column) {
System.out.print("Q ");
}
else {
System.out.print("* ");
}
}
System.out.println();
}
System.out.println();
}
}
总结
回溯算法就是个多叉树的遍历问题，关键就是在前序遍历和后序遍历的位置做一些操作，算法框架如下：
def backtrack(...):
for 选择 in 选择列表:
做选择
backtrack(...)
撤销选择
写 backtrack 函数时，需要维护走过的「路径」和当前可以做的「选择列表」，当触发「结束条件」时，将「路径」记入结果集。
其实想想看，回溯算法和动态规划是不是有点像呢？
某种程度上说，动态规划的暴力求解阶段就是回溯算法。只是有的问题具有重叠子问题性质，可以用 dp table 或者备忘录优化，将递归树大幅剪枝，这就变成了动态规划。而今天的两个问题，都没有重叠子问题，也就是回溯算法问题了，复杂度非常高是不可避免的。