CODEWITHSUNDEEP
javascriptfor-looprecursioncombinations
natecraft1
natecraft1

Reputation: 2846

Trying to return up a recursive combinations function without getting 'undefined'

When I call this with [1,2,3,4], it returns undefined and I'm not understanding why. The goal is for it to return true if any combination of numbers in the array add up to the maximum number in the array, and false if it's not possible.

function ArrayAdditionI(arr) { 

  var max = Math.max.apply(null, arr);
  arr.splice(arr.indexOf(max), 1);
  var sum = function(arr) { return arr.reduce(function(a,b) { return a + b; }); };

  function combos(arr) {

    var f = function(prefix, arr) {
      for (var i = 0; i < arr.length; i++) {
        var clone = prefix.slice(0);
        clone.push(arr[i]);
        if (sum(clone) == max) { return true; }
        return f(clone, arr.slice(i+1));
      }
    }
    return f([], arr);
  }

  return combos(arr); 

}

Upvotes: 0

Views: 127

Answers (3)

Bergi
Bergi

Reputation: 665487

f is returning undefined when it is called with an empty arr! You will need to explicitly return false if none of the tests in the loop returned from the function. And you must not return false on the first occasion of the loop, but break only when you found true and continue the loop elsewhile.

To fix this, you'd have something like

function combos(arr) {
  function f(prefix, arr) {
    for (var i = 0; i < arr.length; i++) {
      var clone = prefix.slice(0);
      clone.push(arr[i]);
      if (sum(clone) == max) return true;
      if (f(clone, arr.slice(i+1))) return true;
    }
    return false;
  }
  return f([], arr);
}

However, also your recursion scheme with the loop looks a bit complicated. I would rather go with the naive enumeration of the "binary tree", where the nodes of each level decide whether the current item will be included in the to-be-tested subset:

function ArrayAdditionI(arr) { 
  var max = Math.max.apply(null, arr);
  arr.splice(arr.indexOf(max), 1);
  var sum = function(arr) { return arr.reduce(function(a,b) { return a + b; }, 0); };

  function f(subset, arr) {
     return arr.length 
          ? f(subset, arr.slice(1)) || f(subset.concat([arr[0]]), arr.slice(1))
          : sum(subset) == max
  }
  return f([], arr); 
}

Upvotes: 2

James
James

Reputation: 4374

The problem is your f function is not ever hitting the if (sum(clone) == max) { return true; } line of code so it will just keep recursively calling until arr.length == 0 and it will return undefined.

Your variables torf and results are unused, maybe you forgot to do something with them?

Upvotes: 0

dpellier
dpellier

Reputation: 1039

It seems that you don't test all the possible combination.

Here you will test 1+2+3, 2+3, 3 but never 1+3.

Do you really want to have a recursive function here ? There may be some more simple way to find that.

function ArrayAdditionI(arr) { 
    var max = Math.max.apply(null, arr);
    arr.splice(arr.indexOf(max), 1);

    var res = arr.filter(function(num, idx) {
        var combination = false;
        // Check all combination non previously tested
        for (var i = idx; i < arr.length - 1; i++) {
            if (num + arr[i+1] === max) {
                combination = true;
                break;
            }
        }
        return combination;
    });
    return res.length > 0;
}

Upvotes: 0

Related Questions