How to count all numeric array elements combinations whose sum is equal to a given value?

Question

The question is in the title.
As an example:

Given this array = [1,1,2,2,3,7,9,1] and sum = 7, I expect this result:

1,1,2,2,1
1,1,2,3
...
7

A quadratic time answer is trivial, I am looking for a sub-quadratic-time solution...
My current sloooow solution:

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

  partial = partial || [];

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

  // check if the partial sum is equals to target
  if (s === target) {
    console.log(partial.join(","))
  }

  if (s >= target) {
    return; // if we reach the number we don't bother to continue
  }

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

subsetSum([1,1,2,2,3,7,9,1], 7);

Output:

1,1,2,2,1
1,1,2,3
1,1,2,3
1,2,3,1
1,2,3,1
1,2,3,1
1,2,3,1
2,2,3
7

For 2k 1-digit numbers, after 4 minutes of crunching, in my box nodejs (v11.14.0) spits out:

FATAL ERROR: Ineffective mark-compacts near heap limit Allocation failed - JavaScript heap out of memory

:-(

please add your answer. what is wrong with it? it looks like a subset sum problem. — Nina Scholz
– Nina Scholz, Commented Nov 8, 2019 at 11:04
For folks who ain't got no larnin' (like me): en.wikipedia.org/wiki/Time_complexity#Sub-quadratic_time — T.J. Crowder
– T.J. Crowder, Commented Nov 8, 2019 at 11:08
At least related: stackoverflow.com/questions/4632322/… See also rosettacode.org/wiki/Count_the_coins — T.J. Crowder
– T.J. Crowder, Commented Nov 8, 2019 at 11:09
It is too slow, however I will add it here, hoping I can clarify what I do mean... — MarcoS
– MarcoS, Commented Nov 8, 2019 at 11:14

Nina Scholz · Accepted Answer · 2019-11-08 11:43:24Z

4

You could take a recursive call by avoiding built in array methods (iteration and most expensive slicing) and take a recursive function which get an index for the next number to get, an array of collected values and a new target, without the last taken value.

This approach returns all possible values, they are not unique, depending on the given data. This approach works for positive numbers only.

function subsetSum(numbers, target) {
    function iter(index, right, delta) {
        if (!delta) return result.push(right);
        if (index >= numbers.length) return;
        if (delta - numbers[index] >= 0)
            iter(index + 1, [...right, numbers[index]], delta - numbers[index]);
        iter(index + 1, right, delta);
    }
    var result = [];
    iter(0, [], target);
    return result;
}

subsetSum([1, 1, 2, 2, 3, 7, 9, 1], 7).map(a => console.log(...a));

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

edited Nov 8, 2019 at 11:43

answered Nov 8, 2019 at 11:33

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

MarcoS Over a year ago

Clever solution. Though, even with only 150 one-digit numbers, Javascript heap is out of memory, on my box... :-(

Nina Scholz Over a year ago

have you eliminated to large values, or too much small same numbers?

MarcoS Over a year ago

I don't get you, sorry... My test numbers are: [6,7,2,5,8,0,1,3,6,3,2,8,7,9,1,5,7,5,1,2,2,3,7,9,4,1,2,2,2,2,3,7,9,4,1,2,2,3,7,9,4,1,2,2,3,7,9,4,1,2,2,3,7,9,4,1,2,2,3,7,9,4,1,2,2,3,7,9,4,1,2,2,3,7,9,4,1,2,2,3,7,9,4,1,2,2,3,7,9,4,1,2,2,3,7,9,4,1,2,2,3,7,9,4,1,2,2,3,7,9,4,1,2,2,3,7,9,4,1,2,2,3,7,9,4,1,2,2,3,7,9,4,1,2,2,3,7,9,4,1,2,2,3,7,9,4]. They are 146, so I can run the algorithm without memory errors...

Nina Scholz Over a year ago

you could filter all values greater than the wanted sum, and eliminates smaller values which sum is greater than the wanted sum.

MarcoS Over a year ago

Yes, thanks... That should be an improvement... But I'm looking for a FASTER and LESS MEMORY CONSUMING solution, if it exists...

Collectives™ on Stack Overflow

How to count all numeric array elements combinations whose sum is equal to a given value?

1 Answer 1

5 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related