Print all sub-arrays with 0 sum

Given an array of integers, it is often required to find all sub-arrays with a sum equal to 0. This problem can be solved using the hashing approach.

Approach: Hashing

The hashing approach involves storing the cumulative sum of the elements in a hash table. If a cumulative sum repeats itself, it indicates that there is a subarray with a sum of 0. We can store the indices where the cumulative sum occurred in a list and print all possible subarrays using these indices.

Here is the algorithm in pseudocode:

1. Create an empty hash table and a list to store indices.
2. Initialize the cumulative sum to 0.
3. Loop through each element in the array: a. Add the current element to the cumulative sum. b. Check if the cumulative sum exists in the hash table. c. If the cumulative sum exists, add its indices to the list. d. If the cumulative sum does not exist, add it to the hash table with its index.
4. Loop through the list of indices: a. Print the subarray between the current index and the previous index.
5. If no subarray is found, print “No subarray found.”

Let’s say we have an array [3, 4, -7, 3, 1, 3, 1, -4] and we want to print all subarrays with a sum equal to 0. Using this algorithm, we would create a hash table to store the cumulative sums:

1. Create an empty hash table: {}
2. Initialize the cumulative sum to 0.
3. Loop through each element in the array: a. Add the current element to the cumulative sum:
   • i. Add 3 to the cumulative sum: 3
   • ii. Check if 3 exists in the hash table. No.
   • iii. Add 3 to the hash table with its index: {3: [0]}
   • iv. Add 4 to the cumulative sum: 7
   • v. Check if 7 exists in the hash table. No.
   • vi. Add 7 to the hash table with its index: {3: [0], 7: [1]}
   • vii. Add -7 to the cumulative sum: 0
   • viii. Check if 0 exists in the hash table. Yes.
   • ix. Add the indices [2,3] to the list.
   • x. Add 3 to the cumulative sum: 3
   • xi. Check if 3 exists in the hash table. Yes.
   • xii. Add the indices [0,4] to the list.
   • xiii. Add 1 to the cumulative sum: 4
   • xiv. Check if 4 exists in the hash table. No.
   • xv. Add 4 to the hash table with its index: {3: [0], 7: [1], 4: [5]}
   • xvi. Add 3 to the cumulative sum: 7
   • xvii. Check if 7 exists in the hash table. Yes.
   • xviii. Add the indices [2,6] to the list.
   • xix. Add 1 to the cumulative sum: 8
   • xx. Check if 8 exists in the hash table. No.
   • xxi. Add 8 to the hash table with its index: {3: [0], 7: [1], 4: [5], 8: [6]}
   • xxii. Add -4 to the cumulative sum: 4
   • xxiii. Check if 4 exists in the hash table. Yes.
   • xxiv. Add the indices [3