在数组中查找可以求和为目标值的可能数字

一尘不染

在数组中查找可以求和为目标值的可能数字

algorithm

给定我有一个数字数组，例如[14,6,10]-如何找到可以加和到给定目标值的可能组合/对。

例如我有 [14,6,10] ，我正在寻找 40 的目标值，我的预期输出将是

 10 + 10 + 6 + 14
 14 + 14 + 6 + 6
 10 + 10 + 10 + 10

*顺序不重要

话虽如此，这是我到目前为止所尝试的：

function Sum(numbers, target, partial) {
  var s, n, remaining;

  partial = partial || [];

  s = partial.reduce(function (a, b) {
    return a + b;
  }, 0);

  if (s === target) {
     console.log("%s", partial.join("+"))
  }


  for (var i = 0; i < numbers.length; i++) {
    n = numbers[i];
    remaining = numbers.slice(i + 1);
    Sum(remaining, target, partial.concat([n]));
  }
}

>>> Sum([14,6,10],40);
// returns nothing

>>> Sum([14,6,10],24);
// return 14+10

它实际上是无用的，因为只有在该数字只能使用一次求和时才会返回。

那怎么办呢？

阅读 232

2020-07-28

共1个答案

一尘不染

只要总和小于所需总和，就可以添加实际索引的值，或者继续下一个索引。

function getSum(array, sum) {

    function iter(index, temp) {

        var s = temp.reduce((a, b) => a + b, 0);

        if (s === sum) result.push(temp);

        if (s >= sum || index >= array.length) return;

        iter(index, temp.concat(array[index]));

        iter(index + 1, temp);

    }



    var result = [];

    iter(0, []);

    return result;

}



console.log(getSum([14, 6, 10], 40));


.as-console-wrapper { max-height: 100% !important; top: 0; }

为了获得有限的结果集，您可以指定长度并在退出条件下进行检查。

function getSum(array, sum, limit) {

    function iter(index, temp) {

        var s = temp.reduce((a, b) => a + b, 0);

        if (s === sum) result.push(temp);

        if (s >= sum || index >= array.length || temp.length >= limit) return;

        iter(index, temp.concat(array[index]));

        iter(index + 1, temp);

    }



    var result = [];

    iter(0, []);

    return result;

}



console.log(getSum([14, 6, 10], 40, 5));


.as-console-wrapper { max-height: 100% !important; top: 0; }

2020-07-28