Javascript函数用于确定数组中数字的任意组合是否合计为最大值

Question

例如：如果arr包含[4，6，23，10，1，3]，则输出应该返回true，因为4 + 6 + 10 + 3 = 23。该数组不会为空，不会包含所有相同的元素，并可能包含负数。
我的尝试
使用递归方法查找arr的所有排列，并添加元素以查看它们是否合计为数组max。该函数正确检查所有排列，但不返回正确的布尔值。

function arrayAddition(arr) { 
    var arrMax = arr.sort(function(a, b) { 
        return a - b; 
       }).pop(); 

    function recArrAdd(sub, arr) { 

     if (arr.length > 0) { 
      var arrSum = sub.concat(arr[0]).reduce(function(prev, curr) { 
       return prev + curr; 
      }); 

      if (arrSum === arrMax) return true; 
      recArrAdd(sub.concat(arr[0]), arr.slice(1)); 
      recArrAdd(sub, arr.slice(1)); 
     } 
     return false; 
    } 

    return recArrAdd([], arr); 
} 

console.log(arrayAddition([1, 2, 3])); 

Answer 1

我认为，问题出在if (arrSum === arrMax) return true;检查。在执行程序arrSum的某些点实际上等于相应的arr[0]。但是当arr[0]碰巧是你的数组中的MAX元素，那么你会得到一个误报。

所以，你必须结合其他检查：if (arr[0] != arrMax)

而且，你的函数不应该返回假当if (arr.length > 0)检查失败。相反，您可以使用全局标志变量（found，如下面的代码所示）并将其作为最终结果返回。

---

编辑：此外，检查if (found) return true;是正确的在recArrAdd()由于性能原因顶部放置：它有助于避免不必要的进一步要求，因为当found是true工作已经完成。

例如，而不它，recArrAdd()称为倍和与它（输入[1,3,5,4,25,8,14]）。

---

这里如下修改后的代码和一些示例输出：使用萤火虫在Firefox

：

function arrayAddition(arr) { 
    var arrMax = Math.max.apply(Math, arr); 
    var found = false; 


    function recArrAdd(sub, arr) { 
     if (found) return true; 
     if (arr.length > 0) { 
      var arrSum = sub.concat(arr[0]).reduce(function(prev, curr) { return prev + curr;}); 
      if (arrSum === arrMax){ 
       if (arr[0] != arrMax){ 
        found = true; 
        return found; 
       } 
      }; 
      recArrAdd(sub.concat(arr[0]), arr.slice(1)); 
      recArrAdd(sub, arr.slice(1)); 
     } 
     return found; 
    } 

    return recArrAdd([], arr); 
} 

console.log("[1,2,3] -> "+arrayAddition([1,2,3])); 
console.log("[1,2,5] -> "+arrayAddition([1,2,5])); 
console.log("[1,2,5,4,20,8] -> "+arrayAddition([1,2,5,4,20,8])); 
console.log("[1,2,5,4,21,8] -> "+arrayAddition([1,2,5,4,21,8])); 
console.log("[1,3,5,4,25,8,14] -> "+arrayAddition([1,3,5,4,25,8,14])); 
console.log("[1,3,5,4,45,8,14] -> "+arrayAddition([1,3,5,4,45,8,14])); 

其产生。

Answer 2

如果你的号码由31界存在着漂亮的解决方案：

让n是最大和arr号码的其余部分。然后将下面的代码检查你想

var mask = 1; 
for (var idx = 0; idx < arr.size; idx++) { 
    mask = mask | mask << arr[idx]; 
} 
return (mask >>> n) & 1; 

什么可以推广使用的boolean而不是位掩码阵列更大的限制。

一些解释。在开始掩码是00000001，标记空集的总和我们可以使0（因为1在位置0）。然后在每一步mask是我们可以做的所有款项的掩码。然后加上arr[idx]为每个总和s我们可以制作s + arr[idx]。所以新款的面具将是mask << arr[idx]。但是我们仍然可以制作全部面具的旧款 - mask。所以掩码的新值是mask | mask << arr[idx]。最后mask是所有可能的总和的掩码，并且如果n是可能的总和，则第n位（(mask >>> n) & 1）是1和0。

Answer 3

您正在寻找这样的事情？：

function sumEqualsMax(values) { 
    var maxValue = Math.max.apply(Math, values); 
    var sumParts = values.slice(); 
    sumParts.splice(sumParts.indexOf(maxValue), 1); 

    var sumValue = sumParts.reduce(function (previousValue, currentValue) { 
     return previousValue + currentValue; 
    }, 0); 

    return sumValue === maxValue; 
} 

var values = [4, 6, 23, 10, 3]; 
console.log(sumEqualsMax(values));