Given I have an array of numbers for example [14,6,10] - How can I find possible binations/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?

Given I have an array of numbers for example [14,6,10] - How can I find possible binations/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?

• javascript
• algorithm
• sum

Share Improve this question Follow asked Feb 9, 2019 at 10:22 user7716943user7716943 49566 silver badges1818 bronze badges 3

• do you have negative numbers as well? – Nina Scholz Commented Feb 9, 2019 at 10:26
• @Nina only positive numbers no negatives – user7716943 Commented Feb 9, 2019 at 10:28
• [14,6,10], so is it that length+1 i.e 4 number bination? Also, what if you have duplicates in your array – Monica Acha Commented Feb 9, 2019 at 10:37

Add a ment  | 

2 Answers 2

Sorted by: Reset to default 6

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

TL&DR : Skip to Part II for the real thing

Part I

@Nina Scholz answer to this fundamental problem just shows us a beautiful manifestation of an algorithm. Honestly it confused me a lot for two reasons

1. When i try [14,6,10,7,3] with a target 500 it makes 36,783,575 calls to the iter function without blowing the call stack. Yet memory shows no significant usage at all.
2. My dynamical programming solution goes a little faster (or may be not) but there is no way it can do above case without exhousting the 16GB memory.

So i shelved my solution and instead started investigating her code a little further on dev tools and discoverd both it's beauty and also a little bit of it's shortings.

First i believe this algorithmic approach, which includes a very clever use of recursion, might possibly deserve a name of it's own. It's very memory efficient and only uses up memory for the constructed result set. The stack dynamically grows and shrinks continuoously up to nowhere close to it's limit.

The problem is, while being very efficient it still makes huge amounts of redundant calls. So looking into that, with a slight modification the 36,783,575 calls to iter can be cut down to 20,254,744... like 45% which yields a much faster code. The thing is the input array must be sorted ascending.

So here es a modified version of Nina's algorithm. (Be patient.. it will take like 25 secs to finalize)

function getSum(array, sum) {
    function iter(index, temp) {cnt++ // counting iter calls -- remove in production code
        var s = temp.reduce((a, b) => a + b, 0);
        sum - s >= array[index]   && iter(index, temp.concat(array[index]));
        sum - s >= array[index+1] && iter(index + 1, temp);
        s === sum                 && result.push(temp);
        return;
    }

    var result = [];
    array.sort((x,y) => x-y); // this is a very cheap operation considering the size of the inpout array should be small for reasonable output.
    iter(0, []);
    return result;
}
var cnt = 0,
    arr = [14,6,10,7,3],
    tgt = 500,
    res;
console.time("bos");
res = getSum(arr,tgt);
console.timeEnd("bos");
console.log(`source numbers are ${arr}
found ${res.length} unique ways to sum up to ${tgt}
iter function has been called ${cnt} times`);

Part II

Eventhough i was impressed with the performance, I wasn't fortable with above solution for no solid reason that i can name. The way it works on side effects and the very hard to undestand double recursion and such disturbed me.

So here es my approach to this question. This is many times more efficient pared to the accepted solution despite i am going functional in JS. We have still have room to make it a little faster with ugly imperative ways.

The difference is;

Given numbers: [14,6,10,7,3] Target Sum: 500

Accepted Answer:

• Number of possible ansers: 172686
• Resolves in: 26357ms
• Recursive calls count: 36783575

Answer Below

• Number of possible ansers: 172686
• Resolves in: 1000ms
• Recursive calls count: 542657

function items2T([n,...ns],t){cnt++ //remove cnt in production code
    var c = ~~(t/n);
    return ns.length ? Array(c+1).fill()
                                 .reduce((r,_,i) => r.concat(items2T(ns, t-n*i).map(s => Array(i).fill(n).concat(s))),[])
                     : t % n ? []
                             : [Array(c).fill(n)];
};

var cnt = 0, result;
console.time("bos");
result = items2T([14, 6, 10, 7, 3], 500)
console.timeEnd("bos");
console.log(`${result.length} many unique ways to sum up to 500
and ${cnt} recursive calls are performed`);

Another important point is, if the given array is sorted descending then the amount of recursive iterations will be reduced (sometimes greatly), allowing us to squeeze out more juice out of this lemon. Compare above with the one below when the input array is sorted descending.

function items2T([n,...ns],t){cnt++ //remove cnt in production code
    var c = ~~(t/n);
    return ns.length ? Array(c+1).fill()
                                 .reduce((r,_,i) => r.concat(items2T(ns, t-n*i).map(s => Array(i).fill(n).concat(s))),[])
                     : t % n ? []
                             : [Array(c).fill(n)];
};

var cnt = 0, result;
console.time("bos");
result = items2T([14, 10, 7, 6, 3], 500)
console.timeEnd("bos");
console.log(`${result.length} many unique ways to sum up to 500
and ${cnt} recursive calls are performed`);