现在作为前端越来越难。只会css，js，html就可以当前端的日子已经过去了。现在前端要学的东西太多，技术更新太快，学了这个框架，过一阵子就被另外的框架代替，又要重新学。了解框架使用还不够，要了解框架本身原理，只会写js不够，还要会写nodejs。会css不够，还要学 less,sass,styus,会写pc端不够，还要会写移动端，小程序。然后当你觉得你可以了，去大厂面试，发现还要会各种数据结构，算法…
害。路还很长，虽然头发越来越少，身体越来越虚，但还得靠着这双手养家糊口，只能硬着头皮走下去…
《前端也有算法系列》第一篇，从leetcood刷题，对于经典的题目或者算法，要坚持写题解以及博客心得，跟大家一起从算法小白慢慢成长。
力扣 第46题：https://leetcode-cn.com/problems/permutations/
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]关于回溯算法，我找到一篇好文，从经典的全排列到8皇后问题，有详细的题解。我这里就按照这篇文章的思路，一步一步的求解全排列问题。
废话不多说，直接上回溯算法框架。解决一个回溯问题，实际上就是一个决策树的遍历过程。你只需要思考 3 个问题：
1、路径：也就是已经做出的选择。
2、选择列表：也就是你当前可以做的选择。
3、结束条件：也就是到达决策树底层，无法再做选择的条件。
如果你不理解这三个词语的解释，没关系，我们后面会用「全排列」和「N 皇后问题」这两个经典的回溯算法问题来帮你理解这些词语是什么意思，现在你先留着印象。
代码方面，回溯算法的框架：
result = [] function backtrack(路径, 选择列表){ if(满足结束条件) { result.add(路径) return; } for(let i = 0 ; i < 选择列表的长度 ;i++) { 做选择 backtrack(路径, 选择列表) 撤销选择 } }其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」，特别简单。
什么叫做选择和撤销选择呢，这个框架的底层原理是什么呢？下面我们就通过「全排列」这个问题来解开之前的疑惑，详细探究一下其中的奥妙！
我们在高中的时候就做过排列组合的数学题，我们也知道 n 个不重复的数，全排列共有 n! 个。
PS：为了简单清晰起见，我们这次讨论的全排列问题不包含重复的数字。
那么我们当时是怎么穷举全排列的呢？比方说给三个数 [1,2,3]，你肯定不会无规律地乱穷举，一般是这样：
先固定第一位为 1，然后第二位可以是 2，那么第三位只能是 3；然后可以把第二位变成 3，第三位就只能是 2 了；然后就只能变化第一位，变成 2，然后再穷举后两位……
其实这就是回溯算法，我们高中无师自通就会用，或者有的同学直接画出如下这棵回溯树：
只要从根遍历这棵树，记录路径上的数字，其实就是所有的全排列。我们不妨把这棵树称为回溯算法的「决策树」。
为啥说这是决策树呢，因为你在每个节点上其实都在做决策。比如说你站在下图的红色节点上：
你现在就在做决策，可以选择 1 那条树枝，也可以选择 3 那条树枝。为啥只能在 1 和 3 之中选择呢？因为 2 这个树枝在你身后，这个选择你之前做过了，而全排列是不允许重复使用数字的。
现在可以解答开头的几个名词：[2] 就是「路径」，记录你已经做过的选择；[1,3] 就是「选择列表」，表示你当前可以做出的选择；「结束条件」就是遍历到树的底层，在这里就是选择列表为空的时候。
如果明白了这几个名词，可以把「路径」和「选择」列表作为决策树上每个节点的属性，比如下图列出了几个节点的属性：
我们定义的 backtrack 函数其实就像一个指针，在这棵树上游走，同时要正确维护每个节点的属性，每当走到树的底层，其「路径」就是一个全排列。
再进一步，如何遍历一棵树？这个应该不难吧。回忆一下之前「学习数据结构的框架思维」写过，各种搜索问题其实都是树的遍历问题，而多叉树的遍历框架就是这样：
function traverse(TreeNode root) { for (let i = 0 ; i < root.children ;i++) { // 前序遍历需要的操作 traverse(child); // 后序遍历需要的操作 } }而所谓的前序遍历和后序遍历，他们只是两个很有用的时间点，我给你画张图你就明白了：
前序遍历的代码在进入某一个节点之前的那个时间点执行，后序遍历代码在离开某个节点之后的那个时间点执行。
回想我们刚才说的，「路径」和「选择」是每个节点的属性，函数在树上游走要正确维护节点的属性，那么就要在这两个特殊时间点搞点动作：
现在，你是否理解了回溯算法的这段核心框架？
for 选择 in 选择列表: // 做选择 将该选择从选择列表移除 路径.add(选择) backtrack(路径, 选择列表) // 撤销选择 路径.remove(选择) 将该选择再加入选择列表我们只要在递归之前做出选择，在递归之后撤销刚才的选择，就能正确得到每个节点的选择列表和路径。
----------------------------此处是分割线--------------------------
照着上面的思路，我写出了如下的代码：
let all = [] function loop(path,canbeSelected) { if(path.length == 3) { all.push(path.slice(0)); return; } while(canbeSelected.length) { path.push(canbeSelected.shift()) loop(path,canbeSelected); canbeSelected.push(path.pop()); } } loop([],[1,2,3]);大家注意，这段代码是错误的。 这里,我按照上面的思路，维护了一份可选择的列表 canbeSelected ,初始值是一个数组[1,2,3]。这段代码大家可以拿去跑一下，因为我维护了canbeSelected这个可选列表，当选择了1,2,3之后，撤销选择的时候出了问题，导致了无限循环。循环是这样的：
1、选择了路径[1,2,3]之后，可选列表变为[]
2、撤销3的选择，可选列表变为[3],路径变为[1,2]
3、选择可选列表的[3],路径变为[1,2,3];
4、回到1
这里我意识到，维护可选列表是不正确的，因为可选列表中需要考虑到已经选择的路径,对于选择[3]之前，由于已经有了1,2,3的选择，就不应该再选择。于是我查看了题解。
let all = [] let nums = [1, 2, 3]; function loop(path) { if (path.length == nums.length) { all.push(path.slice(0)); return; } for (let i = 0; i < nums.length; i++) { if (path.includes(nums[i])) continue; path.push(nums[i]); loop(path); path.pop(); } } loop([]); debugger发现题解稍微做了些变通，没有显式记录「选择列表」，而是通过 nums 和 path 推导出当前的选择列表
所以只需要判断路径中没有选择，就可以放到路径中去
上面我的解法也是可以实现的，大家有兴趣可以添加一下判断条件，虽然较题解略复杂，但是相对来说容易理解。
这里再提供一下动态规划的解法
var permute = function(arr) { let length = arr.length; if (length == 1) { return [arr] } let dp = [ 0, [[arr[0]]] ] for (let i = 2; i <= arr.length; i++) { let tg = []; dp[i-1].map(ds => { let child = ds.slice(0); for (let splice = 0; splice <= ds.length; splice++) { let c_child = child.slice(0); c_child.splice(splice,0,arr[i - 1]); tg.push(c_child) } }) dp[i] = tg; } return dp[arr.length] };这里dp数组的推导主要是依靠插值的想法，即，当前的排列方式等于上一个排列方式，再在每个排列中插入待排的新数字得到新的排列。
大家看下最终的dp数组，就可以明白：
其中 1,2的排列方式是：
[ [1,2], [2,1] ]其中 1,2,3的排列方式是把3插入到 1,2排列的各个位置,即[1,2]得到 [3,1,2],[1,3,2],[1,2,3], [2,1]得到[3,2,1],[2,3,1],[2,1,3]
同理，1,2,3,4则是把4插入到上述1,2,3的全排列中，从而得到dp的推导方式。
作为算法小白，只能以小白的角度看问题。代码写的不正确的，欢迎点评指出。
