Return all possible combinations of numbers in an array whose sum is less than or equal to n

Question

var a = [1,3,6,10,-1];
function combinations(array, n) {
}

combinations(a, 9) // should return...
[[1], [3], [6], [-1], [1,3], [1,6], [1,-1], [3,6], [3,-1], [6, -1], [10, -1], [1,3,-1], [3,6,-1], [1,6,-1], [1,3,6,-1]]

maybe i'm missing some correct answers but you get the idea. Really dying to know how to solve this!

Answer 1

I would say the problem here is to take the power set of an array, and filter it down to only the elements whose sum is greater than a certain number.

The power set of a set is the set of all subsets of that set. (Say that five times fast and you'll be a mathematician)

For example, the power set of [1] is [[], [1]] and the power set of [1, 2] is [[], [1], [2], [1, 2]].

First I would define a powerSet function like this:

var powerSet = function (arr) {

    // the power set of [] is [[]]
    if(arr.length === 0) {
        return [[]];
    }

    // remove and remember the last element of the array
    var lastElement = arr.pop();

    // take the powerset of the rest of the array
    var restPowerset = powerSet(arr);


    // for each set in the power set of arr minus its last element,
    // include that set in the powerset of arr both with and without
    // the last element of arr
    var powerset = [];
    for(var i = 0; i < restPowerset.length; i++) {

        var set = restPowerset[i];

        // without last element
        powerset.push(set);

        // with last element
        set = set.slice(); // create a new array that's a copy of set
        set.push(lastElement);
        powerset.push(set);
    }

    return powerset;
};

Then I would define a function that takes the power set of the array and only includes elements whose sum is less than or equal to some amount:

var subsetsLessThan = function (arr, number) {

    // all subsets of arr
    var powerset = powerSet(arr);

    // subsets summing less than or equal to number
    var subsets = [];

    for(var i = 0; i < powerset.length; i++) {

        var subset = powerset[i];

        var sum = 0;
        for(var j = 0; j < subset.length; j++) {
            sum += subset[j];
        }

        if(sum <= number) {
            subsets.push(subset);
        }
    }

    return subsets;
};

This might not be fast on large arrays, but it works well for small ones.

It looks like it gives the right answer for console.log(subsetsLessThan([1,3,6,10,-1], 9));

edit: a little more about the power set function as implemented here

The only subset of [] is [], so the power set of [] is a set containing only []. That would be [[]].

The initial if statement in the powerSet function immediately returns [[]] if you pass in [].

var powerSet = function (arr) {

    if(arr.length === 0) {
        return [[]];
    }

If you pass in a set with at least one element, the powerSet function begins by removing the last element. For example, if you call powerSet on [1, 2], the variable lastElement will be set to 2 and arr will be set to [1].

    var lastElement = arr.pop();

Then the powerSet function recursively calls itself to get the power set of the "rest" of the list. If you had passed in [1, 2], then restPowerset is assigned to powerSet([1]) which is [[], [1]].

    var restPowerset = powerSet(arr);

We define a variable that's going to hold the power set of what was passed in, here [1, 2]

    var powerset = [];

We loop through every set in restPowerset.

    for(var i = 0; i < restPowerset.length; i++) {

        var set = restPowerset[i];

Any subset of [1] is also a subset of [1, 2] so we add it to the list. That is, [] and [1] are both subsets of [1, 2].

        powerset.push(set);

If you add the element 2 to any subset of [1], that is also a subset of [1, 2], so we add it to the list. Both [2] and [1, 2] are subsets of [1, 2].

        set = set.slice(); // copy the array
        set.push(lastElement); // add the element
        powerset.push(set);

That's all. At this point, the variable powerset is [[], [2], [1], [1, 2]]. Return it!

    }

    return powerset;
};

Answer 2

Brute force O(N*2^N) solution, where N = a.length < 31.

This uses the index i as a bit field to filter the elements of a in each iteration into a sublist.

var a = [1,3,6,10,-1];

function combinations(array, n) {
    var lists = [], M = 1<<array.length;
    for( var i = 1 ; i < M ; ++i ) {
        var sublist = array.filter(function(c,k){return i>>k & 1});
        if( sublist.reduce(function(p,c){return p+c},0) <= n )
            lists.push(sublist);
    }
    return lists;
}

console.log(JSON.stringify(combinations(a,9)));

[[1],[3],[1,3],[6],[1,6],[3,6],[-1],[1,-1],[3,-1],[1,3,-1],[6,-1],[1,6,-1],[3,6,-1],[1,3,6,-1],[10,-1]]