# Find all subarray with sum equal to number?

Could you please tell me how to find all subarray with sum equal to number Example

``````arr[] = [2, 4, 45, 6, 0, 19]
x  =  51
Output: [2,4,45]
``````

Or

``````arr[] = [1, 11, 100, 1, 0, 200, 3, 2, 1, 280]
x = 280
Output: [280]
``````

I tried like that but not getting correct output

``````function getSubArray(arr, num) {
var sum = 0,
blank = [];
var bigArr = []
for (var i = 0; i < arr.length; i++) {
sum = arr[i];
if (blank.length === 0) {
blank.push(arr[i]);
}
for (var j = 1; i < arr.length; j++) {
sum += arr[j];
if (sum < num) {
blank.push(arr[j])
} else if (sum > num) {
sum = 0;
blank = [];
break;
} else {
blank.push(arr[j])
bigArr.push(blank);
sum = 0;
blank = [];
}
}
}

return bigArr
}

console.log(getSubArray([1, 3, 6, 11, 1, 5, 4], 4));``````

for this expected output is

``````console.log(getSubArray([1, 3, 6, 11, 1, 5,4],4));

output: [1,3]
[4]
``````

expected output [[1,3], [4]] is my expected output

On Best Solutions

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

On

Solution

``````'use strict';

function print(arr[], i, j) {
let k = 0;
for (k = i; k <= j; k += 1) {
console.log(arr[k]);
}
}

function findSubArrays(arr[], sum) {
let n = arr.length;
let i;
let j;
let sum_so_far;

for (i = 0; i<n; i+= 1) {
sum_so_far = 0;
for (j = i; j < n; j++) {
sum_so_far += arr[j];

if (sum_so_far === sum) {
print(arr, i, j);
}
}

}
}
``````
On

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

On

This will try every possible permutation of the array (will stop further permutations once limit is reached)

``````function test(arr, num) {
// sorting will improve time as larger values will be eliminated first
arr = arr.sort(function(a, b) {
return b - a;
});
var allLists = [];
var start = Date.now();
helper(0, 0, []);
console.log("Ms elapesed: " + (Date.now() - start));

function helper(start, total, list) {
var result = [];
// Using for loop is faster because you can start from desired index without using filter, slice, splice ...
for (var index = start; index < arr.length; index++) {
var item = arr[index];
// If the total is too large the path can be skipped alltogether
if (total + item <= num) {
// Check lists if number was not included
var test = helper(index + 1, total, list.concat(result)); // remove for efficiency
total += item;
result.push(item);
//if (total === num) index = arr.length; add for efficiency
}
}
if (total === num) allLists.push(list.concat(result));
}
}

console.log(test([2, 4, 45, 6, 0, 19], 51)); // [2,4,45] [2,4,45,0] [6,45] [6,45,0]
console.log(test([1, 11, 100, 1, 0, 200, 3, 2, 1, 280], 280)); // [280] [280,0]``````

If you want to make it more efficient and just return one of the resulted array just comment out the recursive call. You can also un-comment the line that exits the loop once the limit has been reached (will skip 0s).

On

It will give all the available case. And I use the test case of @Nina Scholz

``````const sum = arr => arr.reduce((a,b) => a + b)

function cal(arr, x) {
const rs = []
for (let i = 0; i< arr.length; i++) {
const tmp = []
for (let j=i; j<arr.length; j++ ) {
tmp.push(arr[j])
if(sum(tmp) === x) rs.push([...tmp])
}
}
return rs
}

console.log(cal([1, 11, 100, 1, 0, 200, 3, 2, 1, 280], 280)) // -> [280]
console.log(cal([2, 4, 45, 6, 0, 19], 51)); // -> [2, 4, 45] [45, 6] [45, 6, 0]
console.log(cal([1, 3, 6, 11, 1, 5, 4], 4)); // -> [1,3] [4]``````

On

I would first loop depending on the size of expected arrays.

After that loop for looking for first part of the array which should be filled with positions that will match the desired number.

For example for x= 4 having arr=[5,4,32,8,2,1,2,2,3,4,4] It would first take the 4's. Output will start on [ [4], [4], [4], ..... ] for positions 1,9,10 (respectively)

Then go for the arrays resulting sum of 2 elements [ ... [2,2], [2,2],[2,2], [1,3] ...] ( positions 4+6, position 4+7 position6+7 and position 5+8) You would probably want to use another function to sum and check at this point.

Now will do the same for sum of 3 elements (if any) and so on, having max loop set at number of original array (the resulting number could be the sum of all the elements in the array).

The resulting example would be [ [4], [4], [4], [2,2], [2,2],[2,2], [1,3]]

On

If the question is about finding all subsets (rather than subarrays) with the given cross sum it is also known as the perfect sum problem. https://www.geeksforgeeks.org/perfect-sum-problem-print-subsets-given-sum/

``````
// A recursive function to print all subsets with the
// help of dp[][]. Vector p[] stores current subset.
function printSubsetsRec(arr, i, sum, p)
{
// If we reached end and sum is non-zero. We print
// p[] only if arr[0] is equal to sun OR dp[0][sum]
// is true.
if (i == 0 && sum != 0 && dp[0][sum])
{
p.push(arr[i]);
console.log(p);
return;
}

// If sum becomes 0
if (i == 0 && sum == 0)
{
console.log(p);
return;
}

// If given sum can be achieved after ignoring
// current element.
if (dp[i-1][sum])
{
// Create a new vector to store path
var b = p.slice(0);
printSubsetsRec(arr, i-1, sum, b);
}

// If given sum can be achieved after considering
// current element.
if (sum >= arr[i] && dp[i-1][sum-arr[i]])
{
p.push(arr[i]);
printSubsetsRec(arr, i-1, sum-arr[i], p);
}
}

// Prints all subsets of arr[0..n-1] with sum 0.
function printAllSubsets(arr, sum)
{
var n = arr.length
if (n == 0 || sum < 0)
return;

// Sum 0 can always be achieved with 0 elements
dp = [];
for (var i=0; i<n; ++i)
{
dp[i] = []
dp[i][0] = true;
}

// Sum arr[0] can be achieved with single element
if (arr[0] <= sum)
dp[0][arr[0]] = true;

// Fill rest of the entries in dp[][]
for (var i = 1; i < n; ++i)
for (var j = 0; j < sum + 1; ++j)
dp[i][j] = (arr[i] <= j) ? dp[i-1][j] ||
dp[i-1][j-arr[i]]
: dp[i - 1][j];
if (dp[n-1][sum] == false)
{
console.log("There are no subsets with sum %d\n", sum);
return;
}

// Now recursively traverse dp[][] to find all
// paths from dp[n-1][sum]
var p = [];
printSubsetsRec(arr, n-1, sum, p);
}

printAllSubsets([1,2,3,4,5], 10);
``````
On

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