javascript - Find possible numbers in array that can sum to a target value

Question

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.

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

*Order is not important

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.

So how to do it?

Answer 1

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