回溯法的实质：解决一个回溯的问题，实际上就是一个决策树的遍历过程
回溯法算法框架：
1. 路径：也就是已经做出的选择
2. 选择列表： 也就是你当时可以做的选择
3. 结束条件： 也就是到达决策树底层，无法再做选择的条件（决策树已被遍历完）
回溯法算法框架代码呈现：
···
result = []
def backtrack( 路径 ， 选择列表 ）：
if 满足结束条件：
result.add(路径)；
for 选择 in 选择列表：
做选择
backtrack(路径，选择列表)；//递归
撤销选择 // 只有撤销当前选择，才能遍历决策树的所有路径
···
核心：就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」，但是根据不同题目，可能还要进行不同的剪枝操作
最简单的回溯法：全排列，以[1 , 2 , 3] 为例，先固定第一位为 1，然后第二位可以是 2，那么第三位只能是 3；然后可以把第二位变成 3，第三位就只能是 2 了；然后就只能变化第一位，变成 2，然后再穷举后两位……
其所对应的决策树如下：（选择的每个节点实质上都是在做决策的过程）
当开始穷举时，你可以从1，2，3中选择任意一个数字，如果你现在选择了2这个分支
然后你继续做决策（只能在unvisited的列表中做选择->才能避免重复），可以选择 1 那条树枝，也可以选择 3 那条树枝。为啥只能在 1 和 3 之中选择呢？因为 2 这个树枝在你身后，这个选择你之前做过了，而全排列是不允许重复使用数字的
现在可以解答开头的几个名词：[2] 就是「路径」，记录你已经做过的选择；[1,3] 就是「选择列表」，表示你当前可以做出的选择；「结束条件」就是遍历到树的底层，在这里就是选择列表为空的时候（走到叶子节点了，这时候便可以return了，即当前路径的所有选择已经做完，没有可供选择的路径走了）。
如果明白了这几个名词，可以把「路径」和「选择」列表作为决策树上每个节点的属性，比如下图列出了几个节点的属性：
我们定义的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;
}
public 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.addLast(nums[i]);
//进入下一层决策树
backtrack(nums,track);
//撤销选择，走另一条路（取消当前节点，放入新选择的节点）
track.removeLast();
}
}
···
当然，这个算法解决全排列不是很高效，应为对链表使用contains方法需要 O(N) 的时间复杂度。于是我们通过添加visited数组来对此算法进行改进。（但是必须说明的是，不管怎么优化，都符合回溯框架，而且时间复杂度都不可能低于 O(N!)，因为穷举整棵决策树是无法避免的。这也是回溯算法的一个特点，不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高。）
···
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if(nums == null || nums.length == 0)
return res;
int[] visited = new int[nums.length];
sort(res,nums,new ArrayList<>(),visited);
return res;
}
public void sort(List<List<Integer>> res,int [] nums,List<Integer> cur,int[] visited){
if(cur.size() == nums.length){
res.add(new ArrayList(cur));
return ;
}
for(int i =0;i<nums.length;i++){
if(visited[i]!=0)
continue;
cur.add(nums[i]);
visited[i] =1;
sort(res,nums,cur,visited);
cur.remove(cur.size()-1);
visited[i] = 0;
}
}
···
N皇后问题：
给你一个 N×N 的棋盘，让你放置 N 个皇后，使得它们不能互相攻击。
PS：皇后可以攻击同一行、同一列、左上左下右上右下四个方向的任意单位。
直接套用框架
···
vector<vector<string>> res;
/* 输入棋盘边长 n，返回所有合法的放置 */
vector<vector<string>> solveNQueens(int n) {
// '.' 表示空，'Q' 表示皇后，初始化空棋盘。
vector<string> board(n, string(n, '.'));
backtrack(board, 0);
return res;
}
// 路径：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] = '.';
}
}
···
这部分主要代码，其实跟全排列问题差不多，isValid函数的实现也很简单：
···
/* 是否可以在 board[row][col] 放置皇后？ */
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;
}
···
有的时候，我们并不想得到所有合法的答案，只想要一个答案，怎么办呢？比如解数独的算法，找所有解法复杂度太高，只要找到一种解法就可以。
其实特别简单，只要稍微修改一下回溯算法的代码即可：
···
// 函数找到一个答案后就返回 true
bool backtrack(vector<string>& board, int row) {
// 触发结束条件
if (row == board.size()) {
res.push_back(board);
return true;
}
...
for (int col = 0; col < n; col++) {
board[row][col] = 'Q';
if (backtrack(board, row + 1))
return true;
board[row][col] = '.';
}
return false;
}
```
两种方法的java实现：
···java
public class P51 {
private static List charToString(char[][]array) {
List result =newLinkedList<>();
for(char[] chars :array) {
result.add(String.valueOf(chars));
}
return result;
}
/**
* 思考路径：
* 1. 定位这是backtrack problem
* 2. 思考决策树的构建过程
* 3. 思考回溯的模板
*/
// 决策树的每一层表示棋盘上的每一行；
每个节点可以做出的选择是，在该行的任意一列放置一个皇后。
static class Solution1 {
List<List<Integer>> res;
public List<List<Integer>> solveNQueens(intn) {
if(n <=0)returnnull;
res =newLinkedList<>();
char[][] board =newchar[n][n];
for(char[] chars : board)
Arrays.fill(chars,'.');
backtrack(board,0);
returnres;
}
/**
* 路径：board中小于row的那些行都已经成功放置了皇后
* 可选择列表: 第row行的所有列都是放置Q的选择
* 结束条件: row超过board的最后一行
*
* @param board
* @param row
*/
private void backtrack(char[][] board,int row) {
if(row== board.length) {
res.add(charToString(board));
return;
}
int n = board[row].length;
for(intcol =0; col < n; col++) {
if(!isValid(board,row, col))
continue;
board[row][col] ='Q';
backtrack(board,row+1);
board[row][col] ='.';
}
}
private boolean isValid(char[][] board,int row , int col) {
int rows= board.length;
//checkisvalidincol
for(char[] chars : board)
if(chars[col] =='Q')
returnfalse;
//check isvalide upright
for(inti =row-1, j = col +1; i >=0&& j =0&& j >=0; i--, j--) {
if(board[i][j] =='Q')returnfalse;
}returntrue;
}
}
publicstaticclassSolution2 {
/**
* 优化isValid的查询，通过3个set来分别记录列、主对角线、副对角线上Q的情况，减少迭代的查询
* Key值：colIndex, [r-c], [r + c] 作为set的key
*/
private List<Integer> res =new LinkedList<>();
privateSet colSet =newHashSet<>();
privateSet masterSet =newHashSet<>();
privateSet slaveSet =newHashSet<>();
public List<List<Integer>> solveNQueens(int n) {
char[][] board =newchar[n][n];
for(char[] chars : board)
Arrays.fill(chars,'.');
backtrack(board,0);
return res;
}
/**
* path: board in [0, row -1]
* choices for a row : every cols
* time to end: row == board.length
*
* @param board
* @param row
*/
private void backtrack(char[][] board,introw) {
if(row== board.length) {
res.add(charToString(board));
return;
}
for(int col =0; col < board[row].length; col++) {
if(!isValide(board,row, col))
continue;
updateRecords(board,row, col);
backtrack(board,row+1);
updateRecords(board,row, col);
}
}
private void updateRecords(char[][] board,int row,int col) {
if(colSet.contains(col)) {
board[row][col] ='.';
colSet.remove(col);
masterSet.remove(row- col);
slaveSet.remove(row+ col);
}else{
board[row][col] ='Q';
colSet.add(col);
masterSet.add(row- col);
slaveSet.add(row+ col);
}
}
private boolean isValide(char[][] board,int row,int col) {
return !colSet.contains(col)&& !masterSet.contains(row- col) && !slaveSet.contains(row+ col);
}
@Test
public void test() {
List> res = solveNQueens(4);
for(List list : res) {
for(String str : list)
P.o(str);
P.o("\n");
}
}
}
}
```
