JavaScript - Special case of subset sum algorithm

Question

From a given array of positive integers, I want to know if the sum of E elements from the array is equal to a given number N.

For example, given the array arr = [1, 2, 3, 4] , e = 3 and n = 9. It means if the sum of 3 elements in arr equals to 9. The result is true since 2 + 3 + 4 is equal to 9.

Another example with arr = [1, 2, 3, 4] , e = 2 and n = 7. It is true since 3 + 4 is equal to 7.

I'm trying to resolve it with recursion, but I'm stuck. My idea is to nest loops dynamically to walk through the elements to the array and compare them.

My attempt is this:

function subsetsum(arr, elements, n) {
    loop(arr, elements, n, [], 0);
}

function loop(arr, elements, n, aux, index) {
    if(aux.length != elements) {
        aux[index] = arr.length - 1;
        loop(arr, elements, n, aux, index + 1);
    } else {
        if ((elements - index + 1) < 0) {
            return 0;
        } else {
            if (aux[elements - index + 1] > 0) { 
                aux[elements - index + 1]--;
                loop(arr, elements, n, aux, index); 
            }
        }
    }
}

subsetsum([1, 2, 3, 4], 3, 9));

Answer 1

A related question is at Find the highest subset of an integer array whose sums add up to a given target. That can be modified to restrict the number of elements in the subset as follows:

// Find subset of a, of length e, that sums to n
function subset_sum(a, e, n) {
  if (n < 0)   return null;           // Nothing adds up to a negative number
  if (e === 0) return n === 0 ? [] : null; // Empty list is the solution for a target of 0

  a = a.slice();
  while (a.length) {              // Try remaining values
    var v = a.shift();            // Take next value
    var s = subset_sum(a, e - 1, n - v); // Find solution recursively
    if (s) return s.concat(v);    // If solution, return
  }
}

Answer 2

I've been playing around with this for a while and decided to use a short-cut, mainly the permutation code from this previous SO question.

My code uses basically uses the permutation code to create an array of all the possible permutations from the input array, then for each array (using map) grabs a slice corresponding to the number specified as amount, sums that slice and if it is the same as total returns true.

some then returns the final result as to whether there are any permutations that equals the total.

function checker(arr, amount, total) {
  var add = function (a, b) { return a + b; }
  return permutator(arr).map(function(arr) {
    var ns = arr.slice(0, amount);
    var sum = ns.reduce(add);
    return sum === total;
  }).some(Boolean);
}

checker([1, 2, 3, 4], 3, 9); // true

I've included two demos - 1) a demo showing this code, and 2) code that provides a more detailed breakdown: basically map returns an object containing the slice info, the sum totals and whether the condition has been met.

This is probably not what you're looking for because it's a bit long-winded, but it was certainly useful for me to investigate :)

Edit - alternatively here's a hacked version of that permutation code from the previous question that delivers the results and an array of matches:

function permutator(inputArr, amount, total) {
  var results = [], out = [];

  function permute(arr, memo) {
    var cur, memo = memo || [];
    var add = function (a, b) { return a + b; }

    for (var i = 0; i < arr.length; i++) {
      cur = arr.splice(i, 1);
      if (arr.length === 0) {
        results.push(memo.concat(cur));
      }

      var a = arr.slice();

      // this is the change
      var sum = memo.concat(cur).reduce(add);     
      if (memo.concat(cur).length === amount && sum === total) {
        out.push(memo.concat(cur))
      }

      permute(a, memo.concat(cur));
      arr.splice(i, 0, cur[0]);
    }

    return [results, out];
  }

  return permute(inputArr);
}

permutator([1,2,3,4], 3, 9);

DEMO

Answer 3

If I understand you correctly, the solution of this task must be simple like this:

function subsetsum(arr, countElements, sum) {
  var length = arr.length-1;
  var temp = 0;
  var lastElement = length-countElements; 
  console.log(lastElement);
  for (var i = length; i > lastElement; i--) {
    temp = temp+arr[i];
    console.log('Sum: '+temp);
  }
  if (temp === sum) {
    console.log('True!');
  } else {console.log('False!')}
};
subsetsum([1, 2, 3, 4], 2, 7);