Given an array of integers, check if array contains a sub-array having 0 sum.
Input: {3,4,-7,3,1,3,1,-4,-2,-2}
Output: Sub-array with 0 sum exists
The sub-arrays with a sum of 0 are:
{3,4,-7}
{4,-7,3}
{-7,3,1,3}
{3,1,-4}
{3,1,3,1,-4,-2,-2}
{3,4,-7,3,1,3,1,-4,-2,-2}
The problem doesn't need to display all the sub-arrays that have a sum of 0.
But rather just say whether or not such a sub-array exists.
If anyone is having a hard time understanding how the algorithm works. You basically traverse through the array, and keep adding each element to the sum variable, and each time you store the new value of sum in a set.
Here come’s the tricky part.
[this is front part of the array] [sub array with zero sum] [this is back of the array]
now suppose the sum of the front part of the array was sum1, this would have been stored in our set. And you keep on iterating. When you have reached the end of the sub array with 0 sum, Guess what should be the value of the sum variable be? well it should be sum of the front part + sum of the sub array with sum 0. Which is sum of the front part. There sum would be sum1, which is already present in the set. And the function returns true.
Now what if the sub-array with 0 sum is in the front.
[sub-array with 0 sum] [back part of the array]
We already add 0 to our set before we start iterating. So after iterating over the sub array with contiguous sum the value of sum becomes 0, which is already present in the sub array, so boom shakalaka. You get a true value returned from the function.
