数组求和有多少的可能性组合

注意，数组的条件是不能重复，可以无序，简化数组求和数值的条目不能大于7个，否则内存会溢出。因为组合可能性太多了

好了言归正传，我有一个同事昨天给我出了二道互联网上的题目，感觉很有意思，所以一起奉献上

问题一：给定一个数组arr，不重复的，选出 n 个数的和等于m

问题二：随意给定一个无序的、不重复的数组data，任意抽取n个数，相加和为sum，也可能无解，请写出该函数。

通过审题发现，问题一是多种可能性的，其实这个用下公式即可

    获取所有的可能组合
    如果是[1,2,3,4,5]取出3个，那么可能性就有10种 C(5,3)= C(5,2)
    公式： 
    全排列  P(n,m)=n!/(n-m)!
    组合排列 P(n,m)=n!/m!/(n-m)!
    C(5,2)=5!/2!*3!=5*4*3*2*1/[(2*1)*(3*2*1)]=10
    这是使用了循环加递归做出了组合排序

可是上面的算法我不太喜欢呢，感觉很恶心，于是自己想想其他思路吧~，不过不得不说上面的时间效率很高，把高中数学，大学数学都要捡起来很重要啊

问题二相对简单一些，就是给出了具体的n个数，然后去找对应组合等于sum的方式

看似不同的两题有相同的地方，于是我针对这2题做了个综合算法。都能服务于以上2中问题，具体也需要 分治算法

按照不同功能，完整代码如下：

函数说明

getAllSumProps

• 入参 rets,num,sum

  rets，（Array），是要查找的数组

  num,(Number/String), 给出具体的组合个数，或者传入 '*' 查找所有可能组合

  sum, (Number), 组合后相加等于的数值

• 方法 find

  直接返回构造函数查找的结果集合，数组类型

    //无序不能重复是前提条件
    var _ARY = [10,20,40,30,50,60,500,300,200,100]
    class getAllSumProps{
        constructor(rets,num,sum){
            //初始化入参
            this.rets = rets
            this.num = num
            this.sum = sum
            //定义备用参数
            //都是小于sum的数组进行重排，便于后续使用
            this.avalid = []
            //已经排好的放到此队列中
            this.queen = []
            //开始常规检查
            this.init()
        }
        //校验入参是否正确
        check(){
            let flag = 1
            if(!this.rets || !this.num || this.rets.length == 0 || this.num < 0 || (!this.sum && this.sum != 0)){
                flag = 0
            }
            return flag
        }
        //检查参数是否有特例大于总值,如果有数值直接抛弃
        checkBigerMax(){
            let _this = this
            this.rets.forEach(function (item) {
                if(item <= _this.sum){
                    _this.avalid.push(item)
                }
            })
            _this.avalid.sort(function (a,b) {
                return a - b
            })
        }
        //初始化综合检查
        init(){
            if(!this.check()){
                throw `check arguments rets = ${this.rets} or num = ${this.num} or sum = ${this.sum}`
                return false
            }
            this.checkBigerMax()
        }
        //笛卡尔求值
        getD(num, targetArry){
            //递减执行寻求笛卡尔组合
            num --
            if(num == 0){
                return targetArry
            }
            let _r = targetArry || this.avalid,
                _newr = []
            this.avalid.forEach(function (itemOld) {
                _r.forEach(function (itemNew) {
                    _newr.push(itemOld.length ? itemOld : [itemOld].concat(itemNew.length ? itemNew : [itemNew]))
                })
            })
            return this.getD(num, _newr)
        }
        /*去重复
        * 重复包含两部分，
        * ** 第一部分：同一个item内部数字重复：'1,1,1'或者'1,1,4'
        * ** 第二部分：多个item重复：'1,4,5' 和 '1,5,4' 或者 '5,4,1'是一样的结果
        */
        noRepeat(ret){
            let o = {},
                _this = this,
                _r
            ret.forEach(function (item) {
                item.sort(function (a,b) {
                    return a - b
                })
                _r = [...new Set(item)]
                if(_r.length == _this.num){
                    o[item.join('-')] = {
                        key : item,
                        value : item.reduce((total, current) => total + current)
                    }
                }
            })
            return o
        }
        //挑选数值等于
        equalSum(_args,sum){
            let _this = this
            sum = sum || this.sum
            Object.keys(_args).forEach(function (item) {
                if(_this.sum == _args[item].value){
                  _this.queen.push(_args[item].key)
                }
            })
        }
        //简单求值
        simpleSum(){
            let _this = this
            this.avalid.forEach(function (item) {
                if(item == _this.sum){
                    _this.queen.push([item])
                }
            })
            return _this.queen
        }
        //
        //开始进行系统求值
        rangeAndResult(num){
            let _n = num || this.num
            //第一步根据num获取合法数值的笛卡尔集合
            let _D = this.getD(_n)
            //第二步去除重复的组合
            _D = this.noRepeat(_D)
            //第三步遍历求值符合的加入到queen队列
            this.equalSum(_D)
            //分析结果并返回
            return this.queen
        }
        //求值的入口
        find(){
            if(this.num == '*'){
                let _result = [],
                    _this = this
                this.avalid.forEach(function (item,index) {
                    _this.num = index + 1
                    _result = index == 0 ? _this.simpleSum() : _this.rangeAndResult(index + 1)
                })
                return _result
            }else{
                if(this.num == 1){
                    return this.simpleSum()
                }
                return this.rangeAndResult()
            }
        }



    }
    const getAllResult = new getAllSumProps(_ARY, '*', 100)

    const allBeJoins = getAllResult.find()

    console.log(allBeJoins)

以上的构造函数内部的avalid检测合法数值不要超过7个，否则内存肯定会溢出，因为这是将所有可能的组合全部拿出来再去筛选，虽然费力，但是思路清晰