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

8 Answers

5
Nina Scholz 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]

0
Naveen Vignesh 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);
      }
    }

  }
}
2
Adriani6 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

1
nick zoum 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));
  return allLists || "Not found";

  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).

1
Tam Dc 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]

0
Mbotet 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]]

1
Marcus 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); 
0
paradox 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]]