https://stackoverflow.com/questions/21640437
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianI 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;
};
