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

• jfriend00: Do you require that all remaining numbers add up to the max value or any number of one or more of the remaining numbers add up to the max value? Your question is not quite clear on this topic.
• Guffa: @jfriend00: "if any combination of numbers in the array can be added up to equal the largest number" has to mean that any number of remaining numbers can be added, as adding all remaining numbers in different arrangements always gives the same sum. Also, the example shows how four of the five remaining numbers are added.
• jfriend00: @Guffa - I read that, but then their own answer they did not even attempt to look at anything but the total of all the numbers. Thus I asked for the OP's comment on that which they did not provide. I never understand why someone posts a question and then disappears - not answering clarifying questions that people might ask.
• Guffa: @jfriend00: The code is not from Coderbyte, it's from the OP. Coderbyte doesn't provide any code. The code doesn't only look at the total of all numbers, it actually checks the sum after each number is added, so in the special case where numbers at the end should be excluded to get the right sum it would actually work.
• jfriend00: @Guffa - The code the OP used doesn't come even close to testing if any combination works. I repeat, it isn't entirely clear what the OP wants and the OP has not responded to the question I posted 19 hrs ago. I will move on. No point in wasting my time when the OP won't answer a simple clarifying question.

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

• Nathan: This is great! Thanks, I'll work on it again over the next few days and see what I can come up with. If you have any suggestions on simple and concrete introductions to recursion, please pass them along. I have reviewed several sources, but they often present the idea in a mathematical or pseudocode format, which makes it even more impenetrable.
• Guffa: @Nathan: Re·cur·sion [n] See recursion. ;) Perhaps a hands-on introduction like this is what you are looking for: codecademy.com/courses/javascript-lesson-205 A little basic to begin with, but it shows recursion using actual code.
• Flambino: @Guffa Off-topic, but if you google "recursion", Google will say "Did you mean 'recursion'?" ;)