在数组中查找可以求和为目标值的可能数字 [英] Find possible numbers in array that can sum to a target value

问题描述

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

Given I have an array of numbers for example [14,6,10] - How can I find possible combinations/pairs that can add upto a given target value.

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

for example I have [14,6,10], im looking for a target value of 40 my expected output will be

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

*顺序并不重要

说，这是我到目前为止所尝试的：

With that being said, this is what I tried so far:

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

实际上是没有用的，因为只有在数字只能使用一次求和。

It is actually useless since it will only return if the number can be used only once to sum.

那怎么办？

推荐答案

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

You could add the value of the actual index as long as the sum is smaller than the wanted sum or proceed with the next index.

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; }

要获得有限的结果集，可以指定长度并在退出条件下检查它。

For getting a limited result set, you could specify the length and check it in the exit condition.

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; }

这篇关于在数组中查找可以求和为目标值的可能数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！