javascript - 尝试返回递归组合函数而不得到 'undefined'

Question

当我用 [1,2,3,4] 调用它时，它返回未定义，我不明白为什么。目标是如果数组中的任何数字组合加起来达到数组中的最大数字，则返回 true，如果不可能，则返回 false。

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

}

Answer 1

当使用空的arr调用

f时，它返回undefined!如果循环中的测试均未从函数返回，您将需要显式返回 false。并且您不能在第一次循环时返回 false，而只能在找到 true 时中断，并在其他时候继续循环。

要解决这个问题，你需要类似的东西

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

但是，您的循环递归方案看起来也有点复杂。我宁愿采用“二叉树”的朴素枚举，其中每个级别的节点决定当前项目是否包含在要测试的子集中:

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