3

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

:-(

MarcoS
  • 17,323
  • 24
  • 96
  • 174
  • 3
    please add your answer. what is wrong with it? it looks like a subset sum problem. – Nina Scholz Nov 08 '19 at 11:04
  • 1
    It is too slow! – MarcoS Nov 08 '19 at 11:05
  • You need to include it anyway, not least so people know what you're saying you *don't* want. – T.J. Crowder Nov 08 '19 at 11:06
  • 1
    For folks who ain't got no larnin' (like me): https://en.wikipedia.org/wiki/Time_complexity#Sub-quadratic_time – T.J. Crowder Nov 08 '19 at 11:08
  • 1
    At least related: https://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum See also https://rosettacode.org/wiki/Count_the_coins – T.J. Crowder Nov 08 '19 at 11:09
  • 1
    It is too slow, however I will add it here, hoping I can clarify what I do mean... – MarcoS Nov 08 '19 at 11:14
  • 1
    I added a snippet with my current solution. – MarcoS Nov 08 '19 at 11:21
  • Does this answer your question? [Find possible numbers in array that can sum to a target value](https://stackoverflow.com/questions/54605306/find-possible-numbers-in-array-that-can-sum-to-a-target-value) – Redu Nov 11 '19 at 17:55
  • Check [my post](https://stackoverflow.com/a/55383423/4543207) that I have given above against your test case array with 146 items. Just filter out the items above the target value (7) and **do not** sort your list (as advised in my answer) either ascending or descending and it will solve your 146 items test case for target 7 in about 4:21 in my humble AMD PC returning 4,259,351 solutions. No memory clogging. – Redu Nov 11 '19 at 22:00

1 Answers1

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; }
Nina Scholz
  • 376,160
  • 25
  • 347
  • 392
  • Clever solution. Though, even with only 150 one-digit numbers, Javascript heap is out of memory, on my box... :-( – MarcoS Nov 08 '19 at 13:18
  • have you eliminated to large values, or too much small same numbers? – Nina Scholz Nov 08 '19 at 13:20
  • 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... – MarcoS Nov 08 '19 at 13:23
  • you could filter all values greater than the wanted sum, and eliminates smaller values which sum is greater than the wanted sum. – Nina Scholz Nov 08 '19 at 13:26
  • Yes, thanks... That should be an improvement... But I'm looking for a FASTER and LESS MEMORY CONSUMING solution, if it exists... – MarcoS Nov 08 '19 at 13:28