natecraft1 - 4 months ago 12

Javascript 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

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;
};
```