关于算法:前端电商-sku-的全排列算法

需要

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

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’,’ 彩色 ’]

进入递归函数:

解决属性数组的下标 0: 假如咱们在第一次循环中抉择了 iphone XS 那此时咱们有一个未实现的后果状态, 假如咱们叫它 prev, 此时 prev = [‘iphone Xs’]。
解决属性数组的下标 1: 那么就解决到 colors 数组的了, 并且咱们领有 prev, 在遍历 colors 的时候持续递归的去把 prev 拼接成 prev.concat(color), 也就是[‘iphoneXs’,’ 彩色 ’] 这样持续把这个 prev 交给下一次递归
解决属性数组的下标 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('~')

关于算法:前端电商-sku-的全排列算法

类似题型

数组总和

思路

Just My Socks（注册教程内含优惠码）

关于算法:前端电商-sku-的全排列算法

类似题型

数组总和

思路

Just My Socks（注册教程 内含优惠码）

Just My Socks（注册教程内含优惠码）