javascript - 组合是解决这个难题的方法吗？

Question

这是 Coderbyte 的“简单”部分的练习。

让函数 ArrayAdditionI(arr) 获取数字数组，如果数组中的任何数字组合可以相加等于数组中的最大数字，则返回“true”，否则返回“false”。例如：如果 arr 包含 [4, 6, 23, 10, 1, 3]，则输出应返回 true，因为 4 + 6 + 10 + 3 = 23。

我可以想象一个交互式解决方案，但复杂性让我感到恐惧。我需要学习什么来解决这个问题？

我正在阅读组合函数 C(n,k)。那是正确的道路吗？

Answer 1

我认为这是一维装箱或背包问题。这个问题也是一个决策问题，所以它是一个 np 问题。这可能是一个弱多项式问题。

Answer 2

也许有一个非常幼稚的解决方案：

arrAddition = function(values) {
    // sort from largest
    values.sort(function(a, b) {
        return b-a;
    }); 
    var sum = 0;
    // starts from second, and add until reaching the limit
    for (var i = 1; i < values.length; i++) {
        sum += values[i];
        if (sum == values[0]) {
            return true;
        } else if (sum > values[0]) {
            // don't go further
            return false;
        }
    }
    // or fail.
    return false
}

使用Underscore方便的方法（如 reduce），它甚至更短。

但我可能完全误解了这个问题......