Print all subarrays with a given sum k in an array

An algorithm to print all subarrays with a given sum k in an array.

Example

Input:
[3,4,-7,1,3,3,1,-4]
k = 7

Output:
[3, 4]
[3, 4, -7, 1, 3, 3]
[1, 3, 3]
[3, 3, 1]

Brute Force Method (Naive Approach) O(n^2) to print all the subarrays with given sum

Implementation

• We are going to traverse and sum all the subarrays of the given array and check if they equal to the given sum k.
• If they are equal then we are going to print them.
• Everything will be written in ES6.

function printSubArrays(arr, k){
   //get the size the of the array
   let length = arr.length;
   
   //traverse through the array
   for(let i = 0; i < length; i++){
      //temp variables to store the sum and elements
      let tempArr = [];
      let sum = 0;
     
      //traverse through the every next element after i
      for(let j = i; j < length; j++){    
         sum += arr[j];
         tempArr.push(arr[j]);
         
         //if sum is equal to k then print the array.
         if(sum === k){
           console.log(tempArr);
         }
      }
   }
}

printSubArrays([3,4,-7,1,3,3,1,-4], 7);

Output:
(2) [3, 4]
(6) [3, 4, -7, 1, 3, 3]
(3) [1, 3, 3]
(3) [3, 3, 1]
//How it works
/*
 length = arr.length = 8;
 loop
  i = 0; i < 8; i++
  tempArr = []; 
  sum = 0;
    loop
    j = i = 0; j < 8; j++
    sum += arr[j] =  0 + 3 = 3;
    tempArr.push(arr[j]) = [3];
    if(3 === 7){
       //condition fails so continue
    }
    
    j = i = 1; j < 8; j++
    sum += arr[j] = 3 + 4 = 7;
    tempArr.push(arr[j]) = [3, 4];
    if(7 === 7){
       console.log([3, 4]);
    }
    
    //continue this till the last element in the inner loop and then check again through next element in parents loop 
 */

Time complexity: O(N ^ 2).
Space complexity: O(N).

Time and Space complexity

• We traversing twice with inner loop, so Time complexity is O(n^2).
• We are storing the array and in worst case all the items of array can equal to the sum, so Space complexity is O(n).