# Print All Subarrays With 0 Sum in C++

## 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. ## 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…arr[i], and now the same sum is obtained for the current sub-array arr…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. `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);

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 4Subarray found from Index 2 to 6Subarray found from Index 5 to 6Subarray found from Index 6 to 9Subarray found from Index 0 to 10`