数字になるサブセットを見つける最速のアルゴリズムは何ですか？

Question

私は2016年の選挙の結果を予測するモデルを作成しようとしています。私が必要とするアルゴリズムの1つは、最大270の選挙投票を加えることができる州のすべての可能な組み合わせを見つけることです。だから、セットアップは

const electoralVotesToWin = 270; 
const states = [ 
    { Name: "Virginia", ElectoralVotes: 13 }, 
    { Name: "North Carolina", ElectoralVotes: 15 }, 
    ... 
]; 

のようなもので、私の望ましい結果は、私はそれをよりよく説明する必要がある場合、私に教えてください

var stateCombos = [ 
    [ "Virginia", "North Carolina", ... ], 
    [ "Virginia", "North Carolina", ....], 
    ... 
]; 

のようなものです。

は状態のすべてのサブセットを見つけるブルートフォースアプローチよりも良くアルゴリズムはありますか？いずれにしても、ここで誰もエレガントでコンパクトですが、必ずしも効率的なソリューションではありませんか？

Answer 1

これはいくつかのさらなる生の試験を必要とするかもしれないが、（何残りがなくなるまで、あるいはこの実装で）標的に達するまで再帰関数の組み合わせを作成するために使用することができる。

function getStates(arr, rem){  
    var res = [], el; 
    while(arr.length){ 
     [el, ...arr] = arr;   
     if(el.ElectoralVotes >= rem) 
      res.push([el]); //total reached 
     else{ 
     for(var s of getStates(arr,rem - el.ElectoralVotes)) //try to reach total with remainder   
      res.push([el, ...s]); 
     } 
    } 
    return res; 
} 


var res= getStates(states, electoralVotesToWin); 

Test fiddle

はNB、例えば、これだけ名前が押され、単に要素がアレイに押し込まれる行を変更し、使用されたが、唯一の名前を取得するために元のオブジェクトをテストするため

：fiddle