1. Introduction

Finding subarrays in an array that sum to zero is a common problem with various applications. It can be solved efficiently using hashing. The idea is to iterate through the array and for each element, calculate its cumulative sum. If the sum has been seen before, then there is a zero-sum subarray.

2. Program Steps

1. Define a printAllSubarrays function that takes an integer array as its parameter.

2. Utilize a HashMap to store the cumulative sum as a key and a list of indices where this cumulative sum occurs as its value.

3. Iterate through the array, calculating the cumulative sum.

4. For every sum encountered, check if the sum minus zero (i.e., the sum itself) is already a key in the map.

5. If it is, there is a zero-sum subarray that ends at the current index. Print this subarray.

6. Otherwise, add the sum to the map.

7. In the main method, define a sample array and call the printAllSubarrays function.

3. Code Program

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
x
public class ZeroSumSubarray {

    public static void printAllSubarrays(int[] arr) {
        // Create an empty HashMap
        Map<Integer, ArrayList<Integer>> map = new HashMap<>();

        // Create an empty ArrayList of ArrayList to store a list of lists
        ArrayList<ArrayList<Integer>> out = new ArrayList<>();

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

        for (int i = 0; i < arr.length; 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.add(new ArrayList<Integer>(0, i));
            }

            ArrayList<Integer> al = new ArrayList<>();

            // If sum already exists in the map there exists at-least one subarray ending at index i with 0 sum
            if (map.containsKey(sum)) {
                // map[sum] stores starting index of all subarrays
                al = map.get(sum);
                for (int it = 0; it < al.size(); it++) {
                    out.add(new ArrayList<Integer>(al.get(it) + 1, i));
                }
            }
            al.add(i);
            map.put(sum, al);
        }

        // Print all subarrays with 0 sum
        for (int i = 0; i < out.size(); i++) {
            ArrayList<Integer> subArr = out.get(i);
            System.out.println("Subarray [" + subArr.get(0) + ".." + subArr.get(1) + "]");
        }
    }

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

Output:

Subarray [2..4]
Subarray [2..6]
Subarray [5..6]
Subarray [6..9]
Subarray [0..10]

4. Step By Step Explanation

1. The function printAllSubarrays is tasked with identifying all subarrays of an input array arr which sum up to 0.

2. We use a HashMap map to store the cumulative sum encountered so far while iterating over the array.

3. The sum itself is used as a key, and its corresponding value is an ArrayList containing indices where this sum is encountered.

4. The outer ArrayList out stores subarrays (in terms of starting and ending indices) where the cumulative sum is zero.

5. As we iterate through the arr, we keep adding the elements to our cumulative sum.

6. Whenever the sum is zero or is found already in map, a zero-sum subarray is identified.

7. Finally, we print all the identified subarrays using their start and end indices.

Remember, while there are multiple ways to approach this problem, using a HashMap helps in achieving a linear time complexity.