Testing if numbers in the array can be added up to equal the largest number in the array

Question

Okay, here's a challenge at Coderbyte that completely stumped me. I came up with a solution, but I know it is flawed.

Have the function ArrayAdditionI(arr) take the array of numbers stored in arr and return the string true if any combination of numbers in the array can be added up to equal the largest number in the array, otherwise return the string false. For example: if arr contains [4, 6, 23, 10, 1, 3] the output should return true because 4 + 6 + 10 + 3 = 23. The array will not be empty, will not contain all the same elements, and may contain negative numbers.

It is easy enough to find the highest value in the array. If the length of the array was fixed, I could probably come up with a way to test various combinations, but I'm not sure how to handle different arrays. I wonder if the solution involves recursion? Or perhaps there is a way to call a function a number of times depending on the size of the array. Anyway, my "solution" is below. I would love to see a real solution, or if anyone wants to give me some hints, I am happy to give it another try.

function ArrayAdditionI(arr) { 
  var greatest = -100;
  var index = -1;
  var sum = 0;

  for (var i = 0; i<arr.length; i++){
    if (arr[i] > greatest){
      greatest = arr[i];
      index = i;
    }
  }
    arr.splice(i,1)
      for (var i = 0; i<arr.length; i++){
        sum += arr[i];
        if (greatest = sum){
          return true;
        }else{
          return false;
        }
      }
  }

Answer 1

First, let's fix the two bugs in the code.

If the array would contain only numbers below -100, your code would think that -100 was the greatest number, located at index -1. That would make the rest of the code remove the last item of the array instead of the greatest one, and try to sum up the remaining to be -100.

Start with the first item as the greatest instead of -100:

var greatest = arr[0];
var index = 0;

for (var i = 1; i < arr.length; i++){
  if (arr[i] > greatest){
    greatest = arr[i];
    index = i;
  }
}

(That bug would however not change the outcome, as an array of numbers below -100 can't be combined to give the sum -100, and an array of all negative numbers can't form a sum according to the specification.)

The splice is using the variable i instead of index. It should be:

arr.splice(index, 1)

Using recursion is a good idea to find a combination. You can make a function that determines if any combination of items from an array can give a specific sum. The function would loop through the items in the array, and call itself to determine if the remaining items could give the sum when the item is subtracted.

Another alternative is to use a bitmask to represent the combinations. If you count from 1 to 2^arr.length-1 you will get all possible combinations. The bitmask 11101 (decimal 29) would give the winning combination [4, 6, 10, 3] from the array [4, 6, 10, 1, 3].