上一篇 已经讲到了 DFS 一些基础的点，由于 DFS 太重要了，不得不再往前深挖一步！
DFS 是深度搜索，是暴力的，是一条道走到黑的，是一次性搜到底的！那么，搜到底发现没有路了，就得回退去找另外的路，再继续莽着搜！既然要回退，就必须保存走过每个点的所有信息，包括先后顺序；这个回退的过程就叫 回溯。
根据回溯思想，演进到回溯算法来解决寻找问题。看一下wiki对回溯法的解释：
回溯法采用 试错 的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现，现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。
简化理解：回溯算法 = 树的深度优先搜索 + 剪枝函数
- 什么是剪枝函数？ 为了提高搜索效率，在搜索过程中使用约束函数，可以避免无谓地搜索那些已知不含答案状态的子树。如果是最优化问题，还可以使用限界函数剪去那些不可能含有最优解的子树。约束函数和限界函数目的相同，都是为了剪去不必要搜索的子树，减少问题求解所需实际生成的状态结点数，他们统称为剪枝函数。
OK，以上是概念介绍，下面来一道经典之经典之经典的回溯算法题：N皇后
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
输入：n = 4 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入： n = 1 输出： [["Q"]]
N 皇后问题很多时候作为例题出现在教科书中，可以当做理解回溯算法的例题进行学习；
以 4 皇后问题为例，递归树如下：
解题思路：
- 回溯算法的通用解题思路就是在递归之前做选择，在退出递归之前撤销选择；
- 通过恰当的方式将不符合条件的情况剪枝；
回溯三部曲:
- 递归函数参数；
- 递归终止条件；
- 单层搜索的逻辑；
回溯模板：
void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { 处理节点; backtracking(路径，选择列表); // 递归 回溯，撤销处理结果 } }
JavaScript 实现：
var solveNQueens = function(n) { function isValid(row, col, chessBoard, n) { // 检查列 for(let i = 0; i < row; i++) { // 这是一个剪枝 if(chessBoard[i][col] === 'Q') { return false } } // 检查 45度角是否有皇后 for(let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) { if(chessBoard[i][j] === 'Q') { return false } } // 检查 135度角是否有皇后 for(let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) { if(chessBoard[i][j] === 'Q') { return false } } return true } // 存放结果 function transformChessBoard(chessBoard) { let chessBoardBack = [] chessBoard.forEach(row => { let rowStr = '' row.forEach(value => { rowStr += value }) chessBoardBack.push(rowStr) }) return chessBoardBack } let result = [] // 回溯 function backtracing(row,chessBoard) { if(row === n) { // 终止条件 result.push(transformChessBoard(chessBoard)) return } for(let col = 0; col < n; col++) { if(isValid(row, col, chessBoard, n)) { chessBoard[row][col] = 'Q' // 处理节点 backtracing(row + 1,chessBoard) // 递归 chessBoard[row][col] = '.' // 回溯，撤销处理结果 } } } let chessBoard = new Array(n).fill([]).map(() => new Array(n).fill('.')) backtracing(0,chessBoard) return result };
代码作者:carlsun-2，已验证通过；
回溯算法跟 DFS 深度搜索算法都很经典，需同步理解，对比、吸收；
我是掘进安东尼，公众号同名，日拱一卒、日掘一金，再会~
