Skip to content
Advertisement

How to check if any array members can be sum up to the largest of them in JavaScript?

The goal is to create a function that takes an array of numbers as a parameter and checks if the largest of them can be obtained as the sum of any of the other numbers in the array.

One condition is that negative numbers can be a part of the array taken as a parameter.

The problem

The function I came up with sums all the array members except the largest, instead of summing any of them. This is why it fails, as can be seen below

function ArrayAddition(arr) {
  // Sort small to large
  arr = arr.sort((a, b) => a - b);

  // get maximum number
  var max = arr.pop();
  
  // Sum
  var num = 0;
  arr.forEach((item) => {
    num += item
  });

  return max === num;
}

// Correctly return true
console.log(ArrayAddition([5,7,16,1,3]));

// Wronglly retuns false (5 - 2 + 8 = 11)  
console.log(ArrayAddition([2,5,-2,8,11]));

Question

How can I make it work if any array members sum up to the largest?

Advertisement

Answer

After removing the max element from the array, the task now becomes given an array and a target sum(max element) find if there exists any sub-sequence in the array that sums up to the target sum. This problem is identical to the Subset sum problem

The easiest way to solve this is to use the inclusion exclusion principle and solve it in O(2^n) as Mihail’s answer already suggests. There are other ways to solve it more efficiently(have a look at the subset sum problem link)

In the below approach, instead of generating all possible subsets, we only consider the sums of all those subsets. This would save a lot of memory but, the worst time complexity still remains the same which is O(2^n).

function ArrayAddition(arr) {
  // Sort small to large
  arr = arr.sort((a, b) => a - b);

  // get maximum number
  const max = arr.pop();

  // maintain a set of all possible sums
  const sums = new Set();

  // insert 0 into sums set i.e, sum of an empty set {}
  sums.add(0);

  for (const value of arr) {
    const newSums = new Set();

    for (const sum of sums) {
      // new possible sum if we consider the value in a subset
      const newSum = sum + value;

      // we have a subset whose sum is equal to max
      if (newSum === max)
        return true;

      newSums.add(newSum);
    }

    // insert all new possible sums
    for (const sum of newSums)
      sums.add(sum);
  }

  // no subset which adds up to max was found
  return false;
}

console.log(ArrayAddition([5, 7, 16, 1, 3]));

console.log(ArrayAddition([2, 5, -2, 8, 11]));

Explanation of the approach with an example

arr = [5,7,16,1,3]

after sorting and removing the max element we have

arr = [1,3,5,7]
max = 16

now initially the set 'sums' only has 0 (empty set)

sums = { 0 }

after the first iteration

sums = {0, 1} which is {[0], [0 +1]}

after the second iteration

sums = {0, 1, 3, 4} which is {[0], [0+1], [0 +3], [0+1 +3]}

after third iteration

sums = {0, 1, 3, 4, 
        5, 6, 8, 9}

after fourth iteration

sums = {0, 1,  3,  4,  5,  6,  8,  9
        7, 8, 10, 11, 12, 13, 15, 16}

since 16 is a possible sum, we return true
Advertisement