仅使用 Y 数即可得出小于 X 的所有可能性？

假设我有这些数字： [2, 25, 37, 54, 54, 76, 88, 91, 99] （这些是随机的）

我需要找到小于 100 的数字的所有组合。并非所有数字都必须在这些组合中使用。示例：2、2+25+37、54+25

我怎样才能在 JavaScript 中实现这一点？

Thanks

This is a modified version of the Subset sum problem http://en.wikipedia.org/wiki/Subset_sum_problem. Taking the power set is the brute force solution, and while simple, is inefficient for large lists, taking O(2^N) time. Subset-sum is NP-complete, so you can't solve it in less than exponential time, but if you divide and conquer, you can solve it faster in the average case (but not the worst case)¹. What you do is, divide the array into two halves and run the powerset function (from Adam's answer) on each half, except you save the sum of the array with the array (in fact, saving the sum of the array creates a huge performance boost even if you don't split the array, as it lets you eliminate lots of redundant addition):

var sum = ps[j].sum + arr[i] //huge optimization! don't redo all the addition
if (sum < 100) { //don't include this check if negative numbers are allowed
    arrCandidate.sum = sum;
    ps.push(arrCandidate);
}

然后，按总和对每一半的幂集进行排序，按相反方向排序

ps1.sort(function(b,a){return a.sum-b.sum;});
ps2.sort(function(a,b){return a.sum-b.sum;});

现在，您可以遍历这两个列表并返回总和小于 100 的每个数组组合：

var pos1 = 0;
var pos2 = -1;
while (pos1 < ps1.length) {
    var arr1 = ps1[pos1];
    while (pos2 + 1 < ps2.length && ps2[pos2+1].sum+arr1.sum < 100) {
        pos2++;
    }
    for (var i = pos2; i >= 0; i--) {
        result.push(arr1.concat(ps2[i]));
    }
    pos1++;
}

将此与非分割解决方案进行比较的工作基准 http://jsfiddle.net/wdhDy/13/

1. 该解决方案的决策版本（它告诉您，有解决方案吗？）运行时间为 O(2^(N/2))。我预计如果有 O(1) 个解决方案，则运行时间为 O(2^(N/2))；在每个子集都是解决方案的最坏情况下，运行时间为 O(2^N)（与未优化相同）。在我的测试中，在 0 到 99 的大小为 20-50 的随机数列表上，它的速度提高了 2-5 倍（加速与大小成正比，但我不确定通过什么公式）。