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?

CodePudding user response：

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)).

CodePudding user response：

second is correct. you missed the first digit. 2 5 - 2 8 = 13

CodePudding user response：

In this particular approach, instead of generating all possible subsets as suggested by @MihailFeraru we only consider the sums of those subsets.

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;
}

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