natecraft1 - 1 year ago 64
Javascript Question

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

``````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!

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;
};
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download