概念维基百科中对于回溯算法的定义：
回溯法 采用试错的思想，它尝试分步地去解决一个问题 。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效地正确地解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案 。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：
- 找到一个可能存在的正确的答案；
- 在尝试了所有可能的分步方法后宣告该问题没有答案
回溯与动态规划的区别共同点：
用于求解多阶段的决策问题 。多阶段决策问题即：
- 求解一个问题分为很多步骤（阶段）；
- 每一个步骤（阶段）可以有多种选择 。
- 动态规划只需要求我们评估最优解是多少，最优解对应的具体解是什么并不要求 。因此很适合应用于评估一个方案的效果；
- 回溯算法可以搜索得到所有的方案（当然包括最优解），但是本质上它是一种遍历算法，时间复杂度很高 。
全排列
leetcode 46:输入: [1,2,3]
输出: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
回溯算法思路：
文章插图
说明：
- 每一个结点表示了求解全排列问题的不同的阶段，这些阶段通过变量的「不同的值」体现，这些变量的不同的值，称之为「状态」；
- 使用深度优先遍历有「回头」的过程，在「回头」以后， 状态变量需要设置成为和先前一样 ，因此在回到上一层节点的过程中，需要撤销上一次的选择，这个操作称之为「状态重置」；
- 深度优先遍历，借助系统栈空间，保存所需要的状态变量，在编码中只需要注意遍历到相应的结点的时候，状态变量的值是正确的，具体的做法是：往下走一层的时候，path 变量在尾部追加，而往回走的时候，需要撤销上一次的选择，也是在尾部操作，因此 path 变量是一个栈；
- 深度优先遍历通过「回溯」操作，实现了全局使用一份状态变量的效果 。
代码实现：
var permute = function(nums) {let len = nums.length, res= [];if(!len) return res;let used = []; // boolean[]let path = []; //number[]dfs(nums, len, 0, path, used, res);return res;function dfs(nums, len, depth, path, used, res){if(depth === len) {//path是动态数组，不能直接push，需要拷贝一份当前值保存到结果中res.push([...path]);return;}// 针对全排列中下标为depth的位置进行所有可能的尝试for(let i=0; i<len; i++){if(!used[i]){path.push(nums[i]);used[i] = true;// 往下找全排列中的下一个位置dfs(nums, len, depth+1, path, used, res);// 形成一个全排列后，进行回退，尝试其他答案used[i] = false;path.pop();}}}};复制代码- 首先这棵树除了根结点和叶子结点以外，每一个结点做的事情其实是一样的，即：在已经选择了一些树的前提下，在剩下的还没有选择的数中，依次选择一个数，这显然是一个 递归 结构；
- 递归的终止条件是： 一个排列中的数字已经选够了 ，因此我们需要一个变量来表示当前程序递归到第几层，我们把这个变量叫做 depth，或者命名为 index ，表示当前要确定的是某个全排列中下标为 index 的那个数是多少；
- 布尔数组 used，初始化的时候都为 false 表示这些数还没有被选择，当我们选定一个数组的时候，就将这个数组的相应位置设置为 true ，这样在考虑下一个位置的时候，就能够以 O(1) 的时间复杂度判断这个数是否被选择过，这是一种「以空间换时间」的思想 。
N皇后
leetcode 51 如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击
推荐阅读
- 爱国者标准的丰富内涵是什么？
- 让你的旧打印机变身WIFI打印机
- 漠河舞厅讲的什么故事？
- 9 个你可能从未使用过的很棒的 CSS 属性
- 介绍一个谷歌的AI工具库MediaPipe
- 预约纪念币不取的后果是什么？
- SUV哪款车最省油？
- 需要了解的一项攻击技术-高隐匿、高持久化威胁
- 跑步锻炼的最适宜时间段是何时？
- 数据库 SQL 约束之 NOT NULL
