javascript - 查找相加为一个数的子集的最快算法是什么？

Question

我正在尝试创建一个模型来预测 2016 年大选的结果。我需要的一种算法是找到所有可能的州组合，这些组合可以加起来达到 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

注意，为了测试使用了原始对象，但要仅获取名称，只需更改将元素插入数组的行，以便仅插入名称，例如:fiddle