Find all subarray with sum equal to number?
This might not be exactly what's needed - might require tweaking as the logic may be flawed here.
I have commented the code for clarification.
var arr = [1, 3, 6, 11, 1, 5,4]; // Define array
var target = 31; // Define target
// filter the numbers higher than target and sort rest ascending
var withinRange = arr.filter(x => x <= target).sort((a, b) => a - b);
if(arr.reduce((a,b) => a + b) < target) // Check if we have enough numbers to make up that number
throw "The max you can get out of your selection is: " + arr.reduce((a,b) => a + b);
// grab the highest number as a starting point and remove it from our array of numbers
var numbers = [withinRange.pop()];
var toFind = target - getSum(); // get remainder to find
for(var i = withinRange.length - 1; i > -1; i--) // iterate from the top
{
if(toFind == withinRange[i]){ // check if number is exactly what we need
numbers.push(withinRange[i]);
break;
}else if(withinRange[i] <= toFind){ // if number is smaller than what we look for
numbers.push(withinRange[i]);
toFind -= withinRange[i];
}
}
function getSum(){ // sum up our found numbers
if(numbers.length == 0) return 0;
return numbers.reduce((a,b) => a + b);
}
console.log([numbers, [target]]); // print numbers as desired output
console.log(target, getSum()) // print the target and our numbers
function combinations(array) {
return new Array(1 << array.length).fill().map(
(e1,i) => array.filter((e2, j) => i & 1 << j));
}
function add(acc,a) {
return acc + a
}
combinations([2, 4, 45, 6, 0, 19]).filter( subarray => subarray.reduce(add, 0) == 51 )
output
[[2,4,45],[45,6],[2,4,45,0],[45,6,0]]
combinations([1, 11, 100, 1, 0, 200, 3, 2, 1, 280]).filter( subarray => subarray.reduce(add, 0) == 280 )
output
[[280],[0,280]]
You could iterate the array and take either the next element or if no element is taken before omit this element.
function getSubset(array, sum) {
function iter(temp, delta, index) {
if (!delta) result.push(temp);
if (index >= array.length) return;
iter(temp.concat(array[index]), delta - array[index], index + 1);
if (!temp.length) iter(temp, delta, index + 1);
}
var result = [];
iter([], sum, 0);
return result;
}
console.log(getSubset([2, 4, 45, 6, 0, 19], 51)); // [2, 4, 45], [45, 6], [45, 6, 0]
console.log(getSubset([1, 11, 100, 1, 0, 200, 3, 2, 1, 280], 280)); // [280]
console.log(getSubset([1, 3, 6, 11, 1, 5, 4], 4)); // [1, 3], [4]