Print All Subarrays With 0 Sum in C++

May 12, 2022

Print all subarrays with 0 sum

Here, on this page, we will discuss the program to Print all subarrays with 0 sum in C++ Programming language.

A simple solution is to consider all subarrays one by one and check if sum of every subarray is equal to 0 or not. The complexity of this solution would be O(n^2).A better approach is to use Hashing.

Print all subarrays with 0 sum in Cpp

Algorithm :

  • Keep the sum of the elements encountered thus far in a variable (say sum).
    If the current sum is zero, we discovered a subarray beginning at index 0 and ending at index current index.
  • Check to see if the current sum is in the hash table.
  • If the current sum already exists in the hash table, it means that it was the sum of some sub-array elements arr[0]…arr[i], and now the same sum is obtained for the current sub-array arr[0]…arr[j], implying that the sum of the sub-array arr[i+1]…arr[j] must be 0.
  • Insert the current total into the hash table.
Print All Subarrays With 0 Sum
While loop in C 
Run
#include <bits/stdc++.h>
using namespace std;

vector< pair<int, int> > findSubArrays(int arr[], int n)
 {
   // create an empty map
   unordered_map<int, vector<int> > map;

   vector <pair<int, int>> out;

   // Maintains sum of elements so far
   int sum = 0;

   for (int i = 0; i < n; i++)
   {
   // add current element to sum
   sum += arr[i];

   // if sum is 0, we found a subarray starting
   // from index 0 and ending at index i
   if (sum == 0)
   out.push_back(make_pair(0, i));

   if (map.find(sum) != map.end())
   {
     // map[sum] stores starting index of all subarrays
     vector<int> vc = map[sum];
     for (auto it = vc.begin(); it != vc.end(); it++)
     out.push_back(make_pair(*it + 1, i));
   }

   // Important - no else
   map[sum].push_back(i);
  }

   // return output vector
   return out;
  }

   // Utility function to print all subarrays with sum 0
   void print(vector<pair<int, int>> out)
   {
     for (auto it = out.begin(); it != out.end(); it++)
    cout << "Subarray found from Index " <<
    it->first << " to " << it->second << endl;
   }

// Driver code
  int main()
  {
     int arr[] = {6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7};
     int n = sizeof(arr)/sizeof(arr[0]);

     vector<pair<int, int> > out = findSubArrays(arr, n);

    if (out.size() == 0)
      cout << "No subarray exists"; 
    else 
      print(out);

   return 0;
  }

Output

Subarray found from Index 2 to 4
Subarray found from Index 2 to 6
Subarray found from Index 5 to 6
Subarray found from Index 6 to 9
Subarray found from Index 0 to 10
Software Engineering SDLC