Javascript array addition - all combinations

Question

I'm working through Coderbyte's array addition problem:

Using the JavaScript language, 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.

I've come up with the solution below, but for some reason, cannot get the recursion to work. The code correctly identifies arrays where the remaining (non-largest) array elements exactly add up to the largest, but fail otherwise. Any suggestions?

function ArrayAdditionI(arr) { 
  arr = arr.sort(function(a,b) {return b-a});
  match = false;
  largest = arr.shift(arr[0]); 

  function test(a){
    if(eval(a.join("+"))==largest){
      match = true;
      return match}
    else {
      for(i = 0; i < a.length; i++){
        newArr = a.slice();
        newArr.splice(i,1);
        return test(newArr);
      }
    }
  }

  test(arr);
  return match;


}

Amadan · Accepted Answer · 2015-02-03 05:26:06Z

eval is evil. In almost all cases, it can be done without eval, and it will be faster and probably safer. Your

eval(a.join("+"))

can be written as

a.reduce(function(a, b) { return a + b; })

Now that that is out of the way: Your recursion works. Your loop doesn't. On the first pass of the loop, you already return the result, so the second, third etc. iteration of the loop in each recursion never happen.

Here's your code with minor changes:

function ArrayAdditionI(arr) { 
  arr.sort(function(a,b) {return b-a;});
  var largest = arr.shift(); 

  function test(a) {
    var sum = a.reduce(function(a, b) { return a + b; }, 0);
    if (sum == largest) {
      return true;
    } else {
      for (var i = 0; i < a.length; i++) {
        var newArr = a.slice();
        newArr.splice(i,1);
        if (test(newArr)) {
          return true;
        }
      }
      return false;
    }
  }

  return test(arr);
}
var result = ArrayAdditionI([4, 6, 23, 10, 1, 3]);
document.getElementById('result').textContent = result;

<div id="result"></div>

Thanks for the response! This worked like a charm. Out of curiosity, why does the 'for' loop require instantiating 'var i = 0' vs. just 'i = 0'?
for doesn't. But you want var i somewhere in the function (doesn't matter where you put it, but the most readable and sensible would be at the top of the function; if it is only ever used as a loop counter, declaring it in the loop itself is usually acceptable). If you don't, then i "leaks out" and refers to a global variable; leaked global variables could have unintended consequences.

Suchit kumar · Accepted Answer · 2015-02-03 06:01:32Z

you can do this also by separating the two function and checking inside the for loop for test function:

 function ArrayAdditionI(arr) { 
	  arr.sort(function(a,b) {return b-a;});
	  var largest = arr.shift(); 
	  return test(arr,largest);
	}
  function test(a,largest) {
	    if (eval(a.join("+")) == largest) {
	      return true;
	    } else {
	      for (var i = 0; i < a.length; i++) {
	        var newArr = a.slice();
	        newArr.splice(i,1);
	        if (test(newArr,largest)) {//check if test returns true then only return from this method otherwise the last line will return false after whole execution
	          return true;
	        }
	      }
	      return false;
	    }
	  }
	var ar=[4, 6, 23, 10, 1, 3];
	var result = ArrayAdditionI(ar);
	alert(result);

Collectives™ on Stack Overflow

Javascript array addition - all combinations

2 Answers 2

2 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Related