CODEWITHSUNDEEP
javascriptarrays
MarcoS
MarcoS

Reputation: 17711

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

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

:-(

Upvotes: 3

Views: 441

Answers (1)

Nina Scholz
Nina Scholz

Reputation: 386604

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

Upvotes: 4

Related Questions