尝试返回递归组合函数而不会"未定义"

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

f在调用空arr时返回undefined !如果循环中的测试都没有从函数返回，则需要显式地使用return false。并且在第一次循环时不能出现return 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); 
}

Answer 2

看来你没有测试所有可能的组合。

这里你将测试1+2+ 3,2 + 3,3，但永远不会测试1+3。

你真的想要一个递归函数吗?也许有更简单的方法可以找到

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

Answer 3

问题是您的f函数从未击中if (sum(clone) == max) { return true; }行代码，所以它会一直递归调用，直到arr。长度== 0，返回undefined。

你的变量torf和结果是未使用的，也许你忘记对它们做些什么?