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

Question

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?

Answer 1

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

Answer 2

Below is one possible approach (and naive) using bitmasks to generate all subsets of a set. You should be able to use it for a correct solution. It will be a good exercise to optimize it further by reducing memory usage and early exiting.

function allSubsetsWithBitmasks(arr) {
    const n = arr.length;
    const subsets = [];
    
    // there are 2^n subsets for every set
    // every subset can be represented by n bits
    for (let i = 0; i < Math.pow(2, n); i++) {
        const subset = [];
        
        for (let j = 0; j < n; j++) {
            // if j-th bit is on, include arr[j] in the subset
            if (i & (1 << j)) subset.push(arr[j]);
        }
        
        subsets.push(subset);
    }
    
    return subsets;
}

console.log(allSubsetsWithBitmasks([1, 2, 3, 4]));

I encourage you to also code the backtracking solution and also get rid of the .sort() because it introduces an unnecessary logarithmic factor. (sorts are made in O(N log N)).