Zero Sum II - C++ Solution

1. Introduction

The "Zero Sum II" problem extends the classic zero-sum problem by requiring the identification of all distinct contiguous subarrays within an integer array that sum to zero. This problem is a more comprehensive test of a programmer's ability to handle subarrays and utilize efficient algorithms and data structures like hash maps.

Problem

Given an integer array, the objective is to find all contiguous subarrays that sum to zero. The solution should return a set of these subarrays. Unlike the simpler version of the problem, where only the existence of a zero-sum subarray is checked, here we need to enumerate all such subarrays.

2. Solution Steps

1. Use a hash map to store the cumulative sums and their corresponding indices.

2. Traverse the array while maintaining the cumulative sum.

3. For each cumulative sum, check if it is already present in the hash map.

4. If it is, iterate over all indices stored for this sum in the hash map to find the starting points of zero-sum subarrays.

5. Add each found subarray to the result set.

6. If the cumulative sum is not in the map, add it with the current index.

7. Return the set of all found subarrays at the end.

3. Code Program

#include <iostream>
#include <vector>
#include <unordered_map>
#include <set>
using namespace std;

// Function to find all zero-sum subarrays in the given array
set<vector<int>> findAllZeroSumSubarrays(vector<int>& nums) {
    unordered_map<int, vector<int>> sumMap; // Map to store cumulative sums and indices
    set<vector<int>> result; // Set to store all zero-sum subarrays
    int sum = 0; // Cumulative sum of elements

    sumMap[0] = {-1}; // Initialize sumMap with zero sum at index -1
    for (int i = 0; i < nums.size(); i++) {
        sum += nums[i]; // Add current element to cumulative sum
        // Check if this sum is seen before
        if (sumMap.find(sum) != sumMap.end()) {
            for (int start : sumMap[sum]) {
                vector<int> subarray(nums.begin() + start + 1, nums.begin() + i + 1);
                result.insert(subarray); // Add subarray to result
            }
        }
        sumMap[sum].push_back(i); // Add index to sumMap
    }
    return result; // Return the set of zero-sum subarrays
}

int main() {
    vector<int> nums = {3, 4, -7, 3, 1, 3, 1, -4, -2, -2}; // Test array
    set<vector<int>> zeroSumSubarrays = findAllZeroSumSubarrays(nums);

    // Print all zero-sum subarrays
    for (const auto& subarray : zeroSumSubarrays) {
        for (int num : subarray) {
            cout << num << " ";
        }
        cout << endl;
    }
    return 0;
}

Output:

3 4 -7

Explanation:

The program employs a hash map to track the cumulative sums at each index. 

When a sum is encountered again, it indicates the start of a new zero-sum subarray. 

The program then extracts all such subarrays and adds them to a set to ensure uniqueness. 

This approach efficiently captures all distinct zero-sum subarrays in the array, providing a comprehensive solution to the problem.