javascript - 查找数组中元素的子集，当它们相加时等于数组中的任何其他元素

Question

我想用 Javascript 编写一个算法来解决以下问题。

给定以下数组 [1,2,3,4,6]，提供与数组中任何其他元素相等的子集数。

例如：

1+2 = 3
1+3 = 4
2+4 = 6
1+2+3 = 6

答案：4 个子集

我可以计算等于数组中任何其他元素的数对的总和；但是，我找不到等于数组中任何其他元素的 2 个或更多元素 (1+2+3) 的总和。

我将如何为此编写算法？谢谢！

Answer 1

这是一个非常简单的解决方案，应该很容易掌握。请注意，这不是一个非常快的算法，但对于较短的数组，它运行良好。

这个想法是为每个组合生成一个位掩码，然后为每个掩码添加位掩码字符串中由 1 指示的数组中的数字：

console.log("Number of subsets: " + getNumberOfSubsets([1, 2, 3, 4, 6], 2));

function getNumberOfSubsets(numbers, minimumNumbersInSubset) {
    var numberOfBits = Math.pow(2, numbers.length);
    var numOfSubsets = 0;

    for (var i=0;i<numberOfBits;i++) {
        var bitField = i.toString(2);
        while(bitField.length < numbers.length) {
            bitField = "0" + bitField;
        }

        var sum = 0;
        var addedNumbers = [];
        for (j=0;j<bitField.length;j++) {
            if (bitField.charAt(j) == "1") {
                sum += numbers[j];
                addedNumbers.push(numbers[j]);
            }
        }

        if (addedNumbers.length >= minimumNumbersInSubset && numbers.indexOf(sum) !== -1) {
            numOfSubsets += 1;
            console.log("Iteration " + i + ": " +
                        bitField+", " + (addedNumbers.join("+") + "=" + sum));
        }
    }

    return numOfSubsets;
}

在控制台中输出以下内容以显示成功的组合：

Iteration 10: 01010, 2+4=6
Iteration 20: 10100, 1+3=4
Iteration 24: 11000, 1+2=3
Iteration 28: 11100, 1+2+3=6
Number of subsets: 4 

这是一个jsfiddle：http: //jsfiddle.net/9HhSs/