Print All Subarrays With 0 Sum in Java

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 Java 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
class Main
{
  // Function to print all subarrays with a zero-sum
  // in a given array
  public static void printAllSubarrays(int[] nums)
  {
     // consider all subarrays starting from `i`
    for (int i = 0; i < nums.length; i++) 
   { 
   int sum = 0;

    // consider all subarrays ending at `j`
    for (int j = i; j < nums.length; j++)
    {
    // sum of elements so far
    sum += nums[j];

    // if the sum is seen before, we have found a subarray with zero-sum
    if (sum == 0) {
       System.out.println("Subarray [" + i + "…" + j + "]");
     }
   }
 }
}

  public static void main (String[] args)
  {
   int[] nums = { 3, 4, -7, 3, 1, 3, 1, -4, -2, -2 };

   printAllSubarrays(nums);
  }
 }

 

Output

Subarray [0…2]
Subarray [0…9]
Subarray [1…3]
Subarray [2…5]
Subarray [3…9]
Subarray [5…7]
While loop in C