解决的问题：
解决一个回溯问题，实际上就是一个决 策树的遍历过程。回溯算法的一 个特点，不像动态规划存在重叠⼦问题可以优化，回溯算法就是纯暴力穷 举，复杂度一般都很高。
要素：
-
路径：也就是已经做出的选择。
-
选择列表：也就是你当前可以做的选择。
-
结束条件：也就是到达决策树底层，无法再做选择的条件。
模板：
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用 之后「撤销选择」，特别简单。
全排列例子：
问题：
我们在高中的时候就做过排列组合的数学题，我们也知道 n 个不重复的 数，全排列共有 n! 个。 PS：为了简单清晰起见，我们这次讨论的全排列问题不包含重复的数字。
思路：
我们通常的思路是：先固定第一位为 1，然后第二位可以是 2，那么第三位只能是 3；然后可以 把第二位变成 3，第三位就只能是 2 了；然后就只能变化第一位，变成 2， 然后再穷举后两位……
回溯算法，我们高中无师自通就会用，或者有的同学直接画出如 下这棵回溯树：
只要从根遍历这棵树，记录路径上的数字，其实就是所有的全排列。我们不 妨把这棵树称为回溯算法的「决策树」。为啥说这是决策树呢，因为我们在每个节点上其实都在做决策。比如说你站在 下图的红色节点上：
[2] 就是「路径」，记录你已经做过的选 择； [1,3] 就是「选择列表」，表示你当前可以做出的选择；「结束条件」就是遍历到树的底层，在这里就是选择列表为空的时候。
如果明白了这几个名词，可以把**「路径」和「选择」列表作为决策树上每个 节点的属性**，比如下图列出了几个节点的属性：
我们定义的 backtrack 函数其实就像一个指针，在这棵树上游走，同时要 正确维护每个节点的属性，每当走到树的底层，其「路径」就是一个全排列。
再进一步，如何遍历一棵树？这个应该不难吧。各种搜索问题其实都是树的遍历问题，而多叉树的遍 历框架就是这样：
void traverse(TreeNode root) {
for (TreeNode child : root.childern)
// 前序遍历需要的操作
traverse(child);
// 后序遍历需要的操作
}
而所谓的前序遍历和后序遍历，他们只是两个很有用的时间点，我给你画张 图你就明白了：
前序遍历的代码在进入某一个节点之前的那个时间点执行，后序遍历代码在 离开某个节点之后的那个时间点执行。
回想我们刚才说的，「路径」和「选择」是每个节点的属性，函数在树上游 走要正确维护节点的属性，那么就要在这两个特殊时间点搞点动作：
故可以看看回溯算法的这段核心框架：
for 选择 in 选择列表:
# 做选择
将该选择从选择列表移除
路径.add(选择)
backtrack(路径, 选择列表)
# 撤销选择
路径.remove(选择)
将该选择再加入选择列表
我们只要在递归之前做出选择，在递归之后撤销刚才的选择，就能正确得到 每个节点的选择列表和路径。
代码：
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 num : nums) {
// 不合法的
if (track.contains(num)) {
continue;
}
// 做选择
track.add(num);
// 下一层决策树
backtrack(nums, track);
// 取消选择
track.removeLast();
}
}
N皇后例子：
问题：
给你一个 N×N 的棋盘，让你放置 N 个皇后，使得它们不能互相攻击。
PS：皇后可以攻击同一行、同一列、左上左下右上右下四个方向的任意单位。
思路：
这个问题本质上跟全排列问题差不多，决策树的每一层表示棋盘上的每一 行；每个节点可以做出的选择是，在该行的任意一列放置一个皇后。
代码：
vector<vector<string>> res;
bool isValid(vector<string> &board, int row, int col) {
int n = board.size();
// 检查列是否有皇后互相冲突
for (int i = 0; i < n; ++i) {
if (board[i][col] == 'Q')
return false;
}
// 检查右上放
for (int i = row - 1, j = col + 1;
i >= 0 && j < n;
i--, j++) {
if (board[i][j] == 'Q')
return false;
}
// 检查左上方
for (int i = row - 1, j = col - 1;
i >= 0 && j >= 0;
i--, j--) {
if (board[i][j] == 'Q')
return false;
}
return true;
}
// 路径：board 中⼩于 row 的那些行都已经成功放置了皇后
// 选择列表：第 row 行的所有列都是放置皇后的选择
// 结束条件：row 超过 board 的最后一行
void backtrack(vector<string> &board, int row) {
// 触发结束条件
if (row == board.size()) {
res.push_back(board);
return;
}
int n = board[row].size();
for (int col = 0; col < n; ++col) {
//排除不合法选择
if (!isValid(board, row, col)) {
continue;
}
// 做选择
board[row][col] = 'Q';
// 进入下一层决策
backtrack(board, row + 1);
// 撤销选择
board[row][col] = '.';
}
}
/* 输入棋盘边数 n，返回所有合法的放置 */
vector<vector<string>> solveNQueues(int n) {
// '.' 表示空，'Q' 表示皇后，初始化空棋盘。
vector<string> board(n, string(n, '.'));
backtrack(board, 0);
return res;
}