To find minimum elements in array which has sum equals to given value

Question

I am trying to find out the minimum elements in array whose sum equals the given input.I tried for few input sum but was able to find only a pair in first case while I need to implement for more than just a pair.

var arr = [10, 0, -1, 20, 25, 30];
var sum = 45;
var newArr = [];
console.log('before sorting = ' + arr);

arr.sort(function(a, b) {
  return a - b;
});
console.log('after sorting = ' + arr);

var l = 0;
var arrSize = arr.length - 1;

while (l < arrSize) {

  if (arr[l] + arr[arrSize] === sum) {
    var result = newArr.concat(arr[l], arr[arrSize]);
    console.log(result);
    break;
  } else if (arr[l] + arr[arrSize] > sum) {
    arrSize--;
  } else {
    l++;
  }
}

Input Array : [10, 0, -1, 20, 25, 30]

Required Sum: 45

Output: [20, 25]

I am trying for

Required Sum : 59

Output: [10, -1, 20, 30]

Answer 1

This can be viewed as an optimization problem which lends itself well to dynamic programming.

This means you would break it up into a recursion that tries to find the minimum length of increasingly smaller arrays with the sum adjusted for what's been removed. If your array is [10, 0, -1, 20, 25, 30] with a sum of 59 you can think of shortest as the min of:

[10, ... shortest([ 0, -1, 20, 25, 30], 49)
[0,  ... shortest([10, 20, 25, 30], 49), 59)
[-1, ... shortest([10, 0, 20, 25, 30], 60)
... continue recursively

with each recursion, the array gets shorter until you are left with one element. Then the question is whether that element equals the number left over after all the subtractions.

It's easier to show in code:

function findMinSum(arr, n){
    if(!arr) return 
    let min 
    for (let i=0; i<arr.length; i++) {

        /* if a number equals the sum, it's obviously
         * the shortest set, just return it
         */
        if (arr[i] == n) return [arr[i]]     
        
        /* recursively call on subset with
         * sum adjusted for removed element 
         */
        let next = findMinSum(arr.slice(i+1), n-arr[i])
        
        /* we only care about next if it's shorter then 
         * the shortest thing we've seen so far
         */
        if (next){
            if(min === undefined || next.length < min.length){
                min = [arr[i], ...next]
            }
        }
    }
    return min && min  /* if we found a match return it, otherwise return undefined */
}

console.log(findMinSum([10, 0, -1, 20, 25, 30], 59).join(', '))
console.log(findMinSum([10, 0, -1, 20, 25, 30], 29).join(', '))
console.log(findMinSum([10, 0, -1, 20, 25, 30], -5)) // undefined when no sum

This is still pretty computationally expensive but it should be much faster than finding all the subsets and sums.

Answer 2

One option is to find all possible subsets of the array, and then filter them by those which sum to the required value, and then identify the one(s) with the lowest length:

const getMinElementsWhichSum = (arr, target) => {
  const subsets = getAllSubsetsOfArr(arr);
  const subsetsWhichSumToTarget = subsets.filter(subset => subset.reduce((a, b) => a + b, 0) === target);
  return subsetsWhichSumToTarget.reduce((a, b) => a.length < b.length ? a : b, { length: Infinity });
};
console.log(getMinElementsWhichSum([10, 0, -1, 20, 25, 30], 45));
console.log(getMinElementsWhichSum([10, 0, -1, 20, 25, 30], 59));

// https://stackoverflow.com/questions/5752002/find-all-possible-subset-combos-in-an-array
function getAllSubsetsOfArr(array) {
    return new Array(1 << array.length).fill().map(
        (e1,i) => array.filter((e2, j) => i & 1 << j));
}