All possibilities that are less than X using only Y numbers?

Question

Say I have these numbers: [2, 25, 37, 54, 54, 76, 88, 91, 99] (these are random)

And I need to find all combinations of those numbers that are less than 100. Not all numbers have to be used in these combinations. Examples: 2, 2+25+37, 54+25

How can I achieve this in JavaScript?

Thanks

Answer 1

This is a modified version of the 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);
}

Then, you sort each half's power set by the sum, sorting in opposite directions

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

Now, you can go through the two lists and return each combination of arrays whose total sum is less than 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++;
}

Working benchmark comparing this to a non-splitting solution

1. The decision version of this solution (which tells you, is there a solution?) runs in O(2^(N/2)) time. I expect this runs in O(2^(N/2)) if there are O(1) solutions, and O(2^N) time (the same as unoptimized) in the worst case where every subset is a solution. In my tests, it is faster by factors of 2-5 on lists of size 20-50 of random numbers from 0 to 99 (Speedup is proportional to size, but I am unsure of by what formula).