javascript - 从值数组计算附加值匹配

Question

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

我能想出的唯一解决方案是线性的:

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>

这适用于只有两个匹配值的对象(例如，当 value 为 50 时)。但是，如果所有三个都匹配(将 value 设置为 60)，则不会产生任何结果。

有没有办法不使用递归函数调用来解决这个问题？如果是，如何？

Answer 1

您可以生成值数组的所有子集，并根据它们是否匹配来过滤它们。通过这种方式，每个长度都得到了 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);
}