Javascript学算法系列（⼀）--回溯从经典的全排列问题，看回溯算法
序⾔
现在作为前端越来越难。只会css，js，html就可以当前端的⽇⼦已经过去了。现在前端要学的东西太多，技术更新太快，学了这个框架，过⼀阵⼦就被另外的框架代替，⼜要重新学。了解框架使⽤还不够，要了解框架本⾝原理，只会写js不够，还要会写nodejs。会css不够，还要学 less,sass,styus，会写pc端不够，还要会写移动端，⼩程序。然后当你觉得你可以了，去⼤⼚⾯试，发现还要会各种数据结构，算法…
害。路还很长，虽然头发越来越少，⾝体越来越虚，但还得靠着这双⼿养家糊⼝，只能硬着头⽪⾛下去…
《前端也有算法系列》第⼀篇，从leetcood刷题，对于经典的题⽬或者算法，要坚持写题解以及博客⼼得，跟⼤家⼀起从算法⼩⽩慢慢成长。
今天的题⽬
⼒扣 第46题：leetcode-cn/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]，你肯定不会⽆规律地乱穷举，⼀般是这样：学javascript前要学什么
先固定第⼀位为 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 推导出当前的选择列表

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。