JavaScript 递归

Question

目标是找出数组中整数的任意组合是否等于数组中的最大整数。

function ArrayAdditionI(arr) { 
  arr.sort(function(a,b){
    return a - b;
  });
  var largest = arr.pop();
  function recursion(target,array){
    if(array.length === 0){
      return target === 0; 
    }
    var n = array[0];
    array = array.slice(1);
    return recursion(target,array) || recursion(target - n, array);
  }
  return recursion(largest,arr);        
}

这个解决方案似乎可行，但我无法遵循。在递归函数的底部，当它到达 OR 运算符的右侧时，我认为它几乎总是返回 false，但它会继续递归。谁能解释一下？

Answer 1

最后的 or 条件使函数检查所有组合。

该函数从数组中剔除一个数字，然后检查是否可以找到没有该数字或有该数字的解。

例如，如果您有数组 [1,2,3,6] ，让我们按照找到解决方案的递归部分进行操作。代码会先挑出6作为最大的，然后调用递归函数寻找总和 6在 [1,2,3] .

函数将剃掉1 ，然后检查总和是否为 6可以在 [2,3] 中找到，或者如果总和 5 (6-1) 可以在[2,3]中找到.

第二种情况的递归调用将剃掉2从数组中，然后检查总和 5可以在 [3] 中找到，或者如果总和 3 (5-2) 可以在 [3] 中找到.

第二种情况的递归调用将剃掉3从数组(留空)，然后检查是否 3可以在 [] 中找到，或者如果 0 (3-3) 可以在 [] 中找到.

第二种情况的递归调用会匹配函数开头的条件，返回true .