前言前段时间在掘金上看到一个热帖。今天懒得加班了。你会写这两个算法吗？带你去电商写产品中心，里面提到了一个比较有意思的故事，大意是一个看似简单的电商sku全排列组合的算法，但是很多人没能顺利的写出来。面试的时候有一个年轻的毕业生给了一个idea，进去之后还是没有写出来，就羞愧的跑了~其实排列组合是一个很经典的算法，也是一个实用的算法递归回溯的应用。这篇文章是关于我将带你学习一个标准的“排列组合解模板”。耐心看完，你会收获更多。需求需求描述起来很简单，一共有三个数组：letnames=["iPhoneX","iPhoneXS"]letcolors=["black","white"]letstorages=["64g","256g"]需要枚举他们所有的组合，最后得到这样一个数组：[["iPhoneX","black","64g"],["iPhoneX","black","256g"],["iPhoneX","白色","64g"],["iPhoneX","白色","256g"],["iPhoneXS","黑色","64g"],["iPhoneXS","黑色","256g"],["iPhoneXS","White","64g"],["iPhoneXS","White","256g"],]由于这些属性数组是不确定的，所以不能简单地使用三元组暴力循环解决。思路如果我们选择递归回溯的方法来解决这个问题，那么最重要的问题就是设计我们的递归函数。思路分解以上面提到的例子为例，我们当前的属性数组是：names,colors,storages。首先，我们将处理名称数组。显然，对于每一个属性数组，我们都需要遍历它，然后一一选取。然后去结合下一个数组的每一项。我们设计的递归函数接受两个参数：index对应当前正在处理的下标，无论是names还是colors或者storage。prev上次递归拼接后的结果，如['iPhoneX','black']。进入递归函数：处理属性数组的下标0：假设我们在第一次循环中选择了iPhoneXS，那么此时我们有一个未完成的结果状态，假设我们称它为prev，此时prev=['iPhoneXS'].处理属性数组的下标1：那么我们就处理完了colors数组，有了prev。在遍历colors时，继续递归地将prev拼接成prev.concat(color)，即['iPhoneXS','black']所以继续将这个prev交给下一个递归。处理属性数组的下标2：那么我们就处理了storages数组，有了name+color的prev，遍历storages的时候继续递归拼接prev成prev.concat(storage)，即['iPhoneXS','Black','64g']，这时候我们发现要处理的属性数组的下标已经到了尾部，于是把它放入全局结果变量res中作为结果。编码实现letnames=["iPhoneX","iPhoneXS"]letcolors=["black","white"]letstorages=["64g","256g"]letcombine=function(...chunks){letres=[]lethelper=function(chunkIndex,prev){letchunk=chunks[chunkIndex]letisLast=chunkIndex===chunks.length-1for(letvalofchunk){letcur=prev.concat(val)if(isLast){//如果数组的最后一项处理完毕，将拼接结果放入返回值res.push(cur)}else{helper(chunkIndex+1,cur)}}}//从属性数组下标0开始处理//此时prev是一个空数组helper(0,[])returnres}console.log(combine(names,colors,storages))绘制一个基于iPhone的递归树图从X开始的递归树图，当然这道题是一棵有多个根节点的树，请想象一下从iPhoneXS开始的树，子结构是完全一样的。万能模板为什么说这个连接是排列组合的“万能模板”呢？看看LeetCode上的真题。组合7777。组合这是一个中等难度的问题，但实际上是一个比较难的问题：该问题给定两个整数n和k，返回1...n中k个数的所有可能组合。示例：输入：n=4,k=2输出：[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],]解决方案letcombine=function(n,k){letret=[]lethelper=(start,prev)=>{letlen=prev.lengthif(len===k){ret.push(prev)return}for(leti=start;i<=n;i++){helper(i+1,prev.concat(i))}}helper(1,[])returnret}可以看出这个问题与我们解法中的商排列组合的代码如此相似。只需要设计一个递归的辅助函数，接受start数组的起始位置和prev最后的拼接结果作为参数，然后对于每个起始点下标start，先拼接起始位置对应的值，然后连续使用其他剩余的下标标记作为下一次拼接的起点。当prev中间状态的拼接数组达到题目要求的长度k时，放入result数组。优化在这个解决方案中，有一些递归分支显然是不可能得到结果的。每次我们递归时，我们将循环遍历所有<=n的项目作为开始。假设我们要求的数组长度为k=3，最大值n=4。而我们用prev=[1]，然后用n=4作为递归的起点，那显然是不可能的得到结果，因为如果n=4，只剩下4个拼接，最多拼接成[1,4]，不可能满足k=3的条件。所以在进入递归之前，这些“废枝”果断减去。这叫做“剪枝”.push(prev)return}//还有剩余位置需要填充letrest=k-prev.lengthfor(leti=start;i<=n;i++){if(n-i+1
