需要

需要形容起来很简略,有这样三个数组:

let names = ["iPhone",'iPhone xs']

let colors = ['彩色','红色']

let storages = ['64g','256g']

须要把他们的所有组合穷举进去，最终失去这样一个数组：

[  ["iPhone X", "彩色", "64g"],  ["iPhone X", "彩色", "256g"],  ["iPhone X", "红色", "64g"],  ["iPhone X", "红色", "256g"],  ["iPhone XS", "彩色", "64g"],  ["iPhone XS", "彩色", "256g"],  ["iPhone XS", "红色", "64g"],  ["iPhone XS", "红色", "256g"],]

因为这些属性数组是不定项的,所以不能简略的用三重的暴力循环来求解了

思路

如果咱们选用递归溯法来解决这个问题，那么最重要的问题就是设计咱们的递归函数

思路合成

以上文所举的例子来说,比方咱们目前的属性数组就是 names,colors,storages,首先咱们会解决names数组
很显然对于每个属性数组 都须要去遍历它 而后一个一个抉择后再去和下一个数组的每一项进行组合

咱们设计的递归函数接管两个参数

  • index 对应以后正在解决的下标,是names还是colors 或者storage。
  • prev 上一次递归曾经拼接成的后果 比方['iphoneX','彩色']

进入递归函数:

  1. 解决属性数组的下标0:假如咱们在第一次循环中抉择了iphone XS 那此时咱们有一个未实现的后果状态,假如咱们叫它prev,此时prev = ['iphone Xs']。
  2. 解决属性数组的下标1: 那么就解决到colors数组的了,并且咱们领有prev,在遍历colors的时候持续递归的去把prev 拼接成prev.concat(color),也就是['iphoneXs','彩色'] 这样持续把这个prev交给下一次递归
  3. 解决属性数组的下标2: 那么就解决到storages数组的了 并且咱们领有了 name+ color 的prev,在遍历storages的时候持续递归的去把prev拼接成prev.concat(storage) 也就是['iPhoneXS','彩色','64g'],并且此时咱们发现解决的属性数组下标曾经达到了开端，那么就放入全局的后果变量res中，作为一个后果

编码实现

let names = ['iphoneX',"iPhone XS"]let colors = ['彩色','红色']let storages = ['64g','256g']let combine = function(...chunks){    let res = []    let helper = function(chunkIndex,prev){        let chunk = chunks[chunkIndex]        let isLast = chunkIndex === chunks.length -1        for(let val of chunk){            let cur = prev.concat(val)            // ['iphoneX','彩色','64g'],['iphoneX','彩色','256g'],['iphoneX','红色','64g']            if(isLast){                // 如果曾经解决到数组的最初一项 则把拼接的后果放入返回值中                res.push(cur)            }else{                helper(chunkIndex+1,cur)            }        }    }    //从属性数组下标为0开始解决    // 并且此时的prev是一个空数组    helper(0,[])    return res}console.log(combine(names,colors,storages));["iphoneX", "彩色", "64g"]["iphoneX", "彩色", "256g"]["iphoneX", "红色", "64g"]["iphoneX", "红色", "256g"]["iPhone XS", "彩色", "64g"]["iPhone XS", "彩色", "256g"]["iPhone XS", "红色", "64g"]["iPhone XS", "红色", "256g"]

万能模板

给定两个整数n和k 返回1...n中所有可能的k个数的组合
输出: n = 4, k = 2
输入:

[  [2,4],  [3,4],  [2,3],  [1,2],  [1,3],  [1,4],]

解答

let combine = function (n,k){    let ret = []    let helper = (start,prev)=>{        let len = prev.length        if(len === k){            ret.push(prev)            return //[[1,2]]        }        for(let i = start;i<=n;i++){            helper(i+1,prev.concat(i))            //helper(2,[1]) [1,2]            //helper(3,[1]), [1,3]            //helper(4,[1]) [1,4]            //helper(3,[2])  [2,3]            //helper(4,[2])[2,4]            // helper(4,[3])[3,4]        }    }    helper(1,[])    return ret}
  • 能够看出这题和咱们求解电商排列组合的代码居然如此类似 只须要设计一个承受start排列起始地位,prev上一次拼接后果为参数的递归helper函数
  • 而后对于每一个终点下标start,先拼接上start地位对应的值，再一直的再以其余残余的下标作为终点去做下一次拼接。
  • 当prev这个中间状态的拼接数组达到题目的要求长度k后 就放入后果数组中

优化

  • 在这个解法中 有一些递归分支是显著不可能获取到后果的
  • 咱们每次递归都会循环尝试 <= n 的所有项去作为start 假如咱们要求的数组长度k=3,
  • 最大值n=4而咱们以prev = [1], 再去以 n=4为start 作为递归的终点
  • 那么显然是不可能失去后果的，因为n=4的话只剩下4这一项能够拼接, 最多
  • 就拼成[1,4], 不可能满足k=3的条件所以在进入递归之前
  • 就果决的把这些废枝给减掉 这就叫做减枝
let combine = function (n,k){    let ret = []    let helper = (start,prev)=>{        let len = prev.length        if(len === k){            ret.push(prev)            return        }        // 还有rest个地位待填补        let rest = k - prev.length        for(let i = start;i<=n;i++){            if(n-i+1<rest){                continue            }            helper(i+1,prev.concat(i))        }    }    helper(1,[])    return ret}

类似题型

给定一个可能蕴含反复元素的整数数组nums,返回该数组所有可能的子集(幂集)
阐明: 解题不能蕴含反复的子集

输出: [1,2,2]输入:[  [2],  [1],  [1,2,2],  [2,2],  [1,2],  []]

剪枝的思路也是和之前类似的 如果循环的时候发现残余的数字不足以凑成指标长度 就间接剪掉

var subsetsWithDup = function(nums){    let n = nums.length    let res = []    if(!n){        return res    }    nums.sort()    let used = {}    let helper = (start,prev,target)=>{ //0,[],2        if(prev.length === target){            let key = genKey(prev)            if(!used[key]){                res.push(prev)                used[key] = true            }            return        }        for(let i = start; i<= n;i++){            let rest = n - i            let need = target - prev.length            if(rest<need){                continue            }            helper(i + 1,prev.concat(nums[i]),target)//1,[1],2     2,[2],2  3,[2],2                                                    // 2,[1,2],2,  2,[2,2],2                                                    //1,[1,]3    2,[2],3    3,[3],3                                                    //2,[1,2],3   3,[2,2],3                                                      //3,[1,2,3],3          }    }  for(let i = 1;i<=n;i++){      helper(0,[],i) //0,[],3  }  return [[],...res]}function genKey(arr){    return arr.join('~')}

数组总和

给定一个数组candidates和一个指标数target,找出candidates中所有能够使数字和为target的组合candidates中的每个数字在每个组合中只能应用一次

阐明:
所有数字(蕴含指标数) 都是正整数
解集不能蕴含反复的组合

示例 1:输出: candidates = [10,1,2,7,6,1,5], target = 8,所求解集为:[  [1, 7],  [1, 2, 5],  [2, 6],  [1, 1, 6]]示例 2:输出: candidates = [2,5,2,1,2], target = 5,所求解集为:[  [1,2,2],  [5]]
思路
  • 与下面思路相似 只不过因为不须要思考同一个元素重复使用的状况 每次的递归start终点应该是prevStart + 1。
  • 因为数组中可能呈现多个雷同的元素 他们可能会生成雷同的解 比方 [1,1,7]去凑8的时候,可能会用下标为0的1和7去凑8,也可能用下标为1的1和7去凑8
  • 所以在把解放入到数组之前 须要先通过惟一的key去判断这个解是否生成过,然而思考到[1,2,1,2,7]这种状况去凑10,可能会生成[1,2,7]和[2,1,7]
  • 这样程序不同然而后果雷同的解，这是不合乎题目要求的 所以一个简略的办法就是 先把数组排序后再求解 这样就不会呈现程序不同雷同的解了
  • 此时只须要做简略的数组拼接即可生成key[1,2,7]->1~2~7
/** * @param {number[]}candidates * @param {number} target * @return {number[][]} */let combinationSum2 = function(candidates,target){    let res = []    if(!candidates.length){        return res    }    candidates.sort()    let used = {}    let helper = (start,prevSum,prevArr) =>{        // 因为全是正整数  所以一旦和大于目标值了  间接完结本次递归即可        if(prevSUm >target){            return        }        // 目标值达成        if(prevSum === target){            let key = genkey(prevArr)            if(!used[key]){                res.push(prevArr)                used[key] = true            }            return        }        for(let i = start;i<candidates.length; i++){            // 这里还是持续从start自身开始  因为多个反复值是容许的            let cur = candidates[i]            let sum = prevSum + cur            let arr = prevArr.concat(cur)            helper(i + 1,sum,arr)        }    }    helper(0,0,[])    return res}let genKey = (arr)=> arr.join('~')