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

Viewed 478

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

4 Answers

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)1. 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).

So if you have an array of numbers:

var arr = [2, 25, 37, 54, 54, 76, 88, 91, 99]

First filter the array to just that which is less than 100

var filtered = arr.filter(function(val){ return val < 100; });

Now you need to find the power set of those numbers.

It looks like there's a sample of code here that will accomplish that.

Excerpt

function powerset(arr) {
    var ps = [[]];
    for (var i=0; i < arr.length; i++) {
        for (var j = 0, len = ps.length; j < len; j++) {
            ps.push(ps[j].concat(arr[i]));
        }
    }
    return ps;
}

So you'd take

var powerSet = powerset(filtered);

And as some sugar, you could format the result nicely with join

console.log('{' + powerSet.join('}{') + '}');

or if you really want it output as a set of all sets, this would technically be more correct :)

console.log('{ {' + powerSet.join('}{') + '} }');

Here's a WORKING DEMO


EDIT

Sorry, you want the set of all sets whose sum is less than 100. kennebec is right. Ditch the filtering first step, and then modify the powerset method thus, using reduce to quickly see if an array's sum is less than 100:

function powerset(arr) {
    var ps = [[]];
    for (var i=0; i < arr.length; i++) {
        for (var j = 0, len = ps.length; j < len; j++) {
            var arrCandidate = ps[j].concat(arr[i]);
            if (arrCandidate.reduce(function(p, c){ return p + c; }) < 100)
                ps.push(arrCandidate);
        }
    }
    return ps;
}

Here's an UPDATED DEMO

If you want to get only unique combinations you can try something like this...
jsFiddle

(function () {
    "use strict";
    var numbers = [2, 25, 37, 54, 54, 76, 88, 91, 99],
        combinations = [];

    (function () {
        var temp = [],
            len = numbers.length,
            sum = 0;

        for (var i = 0; i < len; i++) {
            temp.length = 0;
            sum = numbers[i];

            if (sum < 100) {
                temp.push(sum);
                add(temp);

                for (var j = 0; j < len; j++) {
                    if (numbers[j] >= 100 || i === j) {
                        continue;
                    }
                    sum += numbers[j];

                    if (sum < 100) {
                        temp.push(numbers[j]);
                        add(temp);
                    } else {
                        sum -= numbers[j];
                    }
                }
            }
        }
    }());

    function add(val) {
        var contains = false,
            temp = null;

        val.sort(function (a, b) {
            return a - b;
        });

        temp = val.join(" ");
        if (combinations.length === 0) {
            combinations.push(temp.split(" "));
            return;
        }

        for (var i = 0; i < combinations.length; i++) {
            if (combinations[i].join(" ") === temp) {
                contains = true;
            }
        }
        if (!contains) {
            combinations.push(temp.split(" "));
        }
    }
}());
Related