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

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

How can I achieve this in JavaScript?

Thanks

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

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

How can I achieve this in JavaScript?

Thanks

• javascript
• arrays
• math
• numbers
• binations

• 7 Sounds like homework :) What have you tried? – adamb Commented Dec 5, 2013 at 17:29
• 1 I'm curious to see the most efficient algorithm here. – Sterling Archer Commented Dec 5, 2013 at 17:30
• @adamb it's not homework. And yes I've tried :( – zombio Commented Dec 5, 2013 at 17:34
• 4 Post the code you have tried – user2033671 Commented Dec 5, 2013 at 17:35
• 6 @zombio Fair enough. This has the traits of a typical HW question posted to SO though in that: 1. The example seems like a classic discrete mathematics 101 problem. 2. There's no code posted. 3. You haven't expressed the slighted indication that you understand what the solution will entail. – adamb Commented Dec 5, 2013 at 17:43

4 Answers 4

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-plete, 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 bination 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 paring 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 acplish 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 binations you can try something like this...
jsFiddle

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

    (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 (binations.length === 0) {
            binations.push(temp.split(" "));
            return;
        }

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

Here's a recursive approach, that also applies to only non-negative array elements:

function subset_sum( list, upper_bound )
{
  if( list.length == 1 ) return list[0] < upper_bound ? [list] : [];
  var new_list = list.slice(0); // copy list
  var elem = new_list.pop();
  var bo = elem < upper_bound ? [[elem]] : []; // A
  if( bo.length )
  {
    var lists = subset_sum( new_list, upper_bound-elem ); // B
    bo = bo.concat( lists.map(function(a) { return a.concat(elem); }) );
  }
  return bo.concat(subset_sum( new_list, upper_bound )); // C
}

var arr = [2, 25, 37, 54, 54, 76, 88, 91, 99];
var bos = subset_sum(arr,100);

Here's the jfiddle: http://jsfiddle/bceHr/4/

The base case is the single-element list, where the answer is itself if and only if the element is less than the upper bound.

The recursive step is divided into 3 mutually exclusive and plete cases, marked A, B, and C above:

• (A) The last element is a singleton set if and only if it is less than the upper_bound.
• (B) All other subsets which include the last element are counted, by recusively applying the function to the list omitting the element, and a new upper_bound decreased by that element.
• (C) All other subsets which exclude the last element are counted, by recursively applying the function to the list using the same upper_bound.

Lastly, there are 26 such binations. Since 54 is included twice, it is repeated in the output as well:

[[99],[91],[2,91],[88],[2,88],[76],[2,76],[54],[37,54],[2,37,54],[25,54],[2,25,54],[2,54],[54],[37,54],[2,37,54],[25,54],[2,25,54],[2,54],[37],[25,37],[2,25,37],[2,37],[25],[2,25],[2]]