组合是解决这个难题的办法吗

Are combinations the solution to this puzzle?

本文关键字：难题 解决 组合      更新时间：2023-09-26

下面是Coderbyte"easy"部分的一个练习。

让函数ArrayAdditionI（arr）取一个数字数组，如果数组中的任何数字组合加起来可以等于数组中的最大数字，则返回"true"，否则返回"false"。例如：如果arr包含[4，6，23，10，1，3]，则输出应返回true，因为4+6+10+3=23。

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

我正在读组合函数C（n，k）。这条路对吗？

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

也许有一个非常天真的解决方案：

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
}

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

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

相关文章：