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

Question

例如:如果 arr 包含 [4, 6, 23, 10, 1, 3] 输出应该返回 true 因为 4 + 6 + 10 + 3 = 23。数组不会为空，不会包含所有相同的元素，并且可能包含负数。
我的尝试
使用递归方法查找 arr 的所有排列并将元素相加以查看它们加起来是否达到数组最大值。该函数正确检查所有排列但不返回正确的 bool 值。

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) 检查失败时，您的函数不应返回 false。相反，您可以使用全局标志变量(found，如下面的代码所示)并将其作为最终结果返回。

---

编辑:此外，出于性能原因，检查 if (found) return true; 被放置在 recArrAdd() 的顶部:它有助于避免不必要的进一步调用，因为当 found 为 true 时，工作就完成了。

例如，没有它，recArrAdd()被调用255次，有它 187(输入 [1,3,5,4,25,8,14])。

---

以下是您修改后的代码和一些示例输出:

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

产生:

在 Firefox 中使用 Firebug。