combination sum from predefined set with the target value

user_10046099 0
Viewed 64

I have the following code. I need all the combinations of numbers from that array whose sum is the target which is 100000. The problem is that the below solution doesn't contain the following pair 20000 40000 40000 . This is because for each recursion, I take out the number (LOOK at the filter functionality). If I don't have filter , then maximum call stack exceeded happens.

So the final mission is to have all the combinations of numbers whose sum is target, each combination should have only 3 numbers, and 0 also participates.

Any idea how to fix it ?

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 && partial.length === 3) {
    console.log("%s=%s", partial.join("+"), target)
  }

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

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

subsetSum([0, 10000, 20000, 30000, 40000, 50000, 60000, 70000, 80000, 90000], 100000);

algorithm javascript
1 Answers

You are correct that it is because you filter out the selected number that you can't get the following output

2000 4000 4000

When you take the filtering out, you will get a stack overflow, because you didn't stop the recursion when partial has a length of 3. So recursive calls that keep adding 0 to partial will never stop recursing... as they never lead to exceeding the target.

So add that to the "base case":

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 && partial.length === 3) {
    console.log("%s=%s", partial.join("+"), target)
  }

  if (s >= target || partial.length === 3) {
    return; // if we reach the number or maximum length don't bother to continue
  }

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

subsetSum([0, 10000, 20000, 30000, 40000, 50000, 60000, 70000, 80000, 90000], 100000);

user_54598390
Related