Print All Subarrays With 0 Sum in Python

All Subarrays with 0 Sum

Here, on this page, we will discuss the program to Print All Subarrays with 0 Sum in Python Programming language.

A simple solution is to consider all subarrays one by one and check if the 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.

All Subarrays with 0 Sum

Algorithm ( Method 1 )

  • 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.
All Subarrays with 0 Sum Python

Python Code

Run
def add(arr, l):
    for i in range(l - 1):
        sum = 0
        for j in range(i, l):
            sum += arr[j]
            if sum == 0:
                print("Subarray found from Index ", i, "to", j)


arr = [6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7]
l = len(arr)
add(arr, l)

Output

Subarray found from Index 0 to 10
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

For similar Questions click on the given button