从值数组计算加性值匹配

方猫

我有一个数值和一个包含多个键控数值的对象。我需要弄清楚对象中的哪些值与加起来的值匹配。

我唯一能想到的解决方案是线性解决方案：

var values={1: 10, 2: 20, 3: 30};
var value=50;
var selected=[];

$.each(values, function(k,v){
    if(v==value)
        selected.push(k);
    $.each(values, function(k2,v2){
        if(v+v2==value) {
            selected.push(k);
        }
    });
});
console.log(selected);

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>

这对于只有两个匹配值（例如，值为50）的对象来说效果很好。但是，如果三个都匹配（将值设置为60），则不会产生任何结果。

有没有一种方法可以解决此问题而无需使用递归函数调用？如果是，怎么办？

乔纳斯·威尔姆斯

您可以生成值数组的所有子集，并根据它们是否匹配进行过滤。通过这种方法，您可以获得O(n^2)每种长度（请注意，这仅适用于少于32个元素的值）：

const results = [];

for(let i = 1; i < Math.pow(2, values.length); i++){
  const subset = values.filter((_, pos) => (i >> pos) & 1);
  if(subset.reduce((a, b) => a + b) === value)
    results.push(subset);
}

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。