javascript - js 无序数组 任意个数 相加之和为定量m？

Question

js
数组：a[n]
定量m
a[0],a[1]......a[n]已知，m已知；
怎样计算出哪几个数相加的和为定量m？最终输出这几个数的index

Answer 1

搜索背包问题

Answer 2

我能想到就是循环遍历，一遍一遍来吧。。

Answer 3

关键词: 01背包问题

Answer 4

背包问题，但要数组2边同时开始遍历，时间复杂度就为n，效率高一倍。

Answer 5

不知道效率怎么样
实现了再说吧~~

function getcombinationAndMatched(initval,array,targetValue,someGroup){
    var result=[];
    var matched=[];
    var startIndex;
    if(someGroup.index.length===0){
        startIndex=-1;
    }else{
        startIndex=someGroup.index[someGroup.index.length-1];
    }
    for(var i=startIndex+1;i<array.length;i++){
        if(initval+array[i]<=targetValue) {
            if(initval+array[i]===targetValue){
                matched.push(someGroup.index.slice(0).concat([i]));
                someGroup.value=targetValue;
                someGroup.index.push(i);
            }else{
                result.push({
                    value:initval+array[i],
                    index:someGroup.index.slice(0).concat([i])
                });
            }
        }else{
            break;
        }

    }
    return {
        matched:matched,
        result:result
    }
}

function getMatchedGroup(groupArray,orgArray,targetValue){
    var matched=[];
    for(var q=0;q<groupArray.length;q++){
        var groupResult=getcombinationAndMatched(groupArray[q].value,orgArray,targetValue,groupArray[q]);
        matched=matched.concat(groupResult.matched);
        if(groupResult.result.length!=0){
            var _matched_=getMatchedGroup(groupResult.result,orgArray,targetValue);
            matched=matched.concat(_matched_);
        }
    }

    return matched;

}


var orgArray=[1,2,3,4,5,6,7,8,9,20,30];
var targetValue=41;
orgArray.sort(function(a, b) {
    return a - b;
});
var subArray=[];
var findIndex=orgArray.findIndex(function(item){
    return item>targetValue;
});

if(findIndex===-1){
    subArray=orgArray;
}else{
    subArray=orgArray.slice(0,findIndex);
}

var result=getMatchedGroup([{
    value:0,
    index:[]
}],subArray,targetValue);
//console.log(result);

result.forEach(function(item){
   console.log(item.map(function(valueIndex){
       return orgArray[valueIndex];
   }).join(','));
});