Find all uninterrupted subsequences whose sum is equal to zero

Question

Say that we have an array of N integers and want to find all subsequences of consecutive elements which have the sum of the equal to zero.

Example:

N = 9
array = [1, -2, 4, 5, -7, -4, 8, 3, -7]

Should output:

as each of the above are the start and end index of the subsequences with sum equal to zero.

I came to the conclusion that there are N * (N + 1) / 2 such possible subsequences which would conclude in O(N^2) complexity if using a naive algorithm that exhaustively searches over all the possible solutions.

I would like to know if there is any way to achieve this in O(N) complexity or something less than O(N^2)?

I am aware of the Subset sum problem which is a NP-complete problem but mine seems to be a bit easier as it only requires subsequences of consecutive elements.

Thank you in advance.

@EugeneSh. oops, indeed `-2 4 5 -7 -4 8 3 -7` is the right one. — Gabriel Ivascu, Dec 08 '14 at 20:22
@runDOSrun Unfortunately, I haven't. Should this be closed as a duplicate? — Gabriel Ivascu, Dec 08 '14 at 20:23
Finding one is not the same problem as finding all. I therefore don't think this is a duplicate. — NPE, Dec 08 '14 at 20:27
I think this one should stay open. The linked question reads too like a "do my work for me" question. This one at least has example inputs and outputs. — Cody Piersall, Dec 08 '14 at 20:28
Also be very careful of the word set - a set has no duplicate elements, (your example has two -7s) and the order is not really significant - also `set` is a keyword so should __not__ be used as a variable name. — Steve Barnes, Dec 08 '14 at 20:28
@SteveBarnes You are right, thank you. I've edited the content accordingly. — Gabriel Ivascu, Dec 08 '14 at 20:55

NPE · Answer 1 · 2014-12-08T20:40:47.303

2

It is worse than you think.

There are potentially Θ(n²) uninterrupted subsequences that add up to zero, as in the following example:

0 0 0 0 0 0 0 0 0

(Here, every subsequence adds up to zero.)

Therefore, any algorithm that prints out the start and end index of all the required subsequences will necessarily have o(n²) worst-case complexity. Printing out their elements will require Θ(n³) time.

edited Dec 08 '14 at 20:40

answered Dec 08 '14 at 20:23

NPE

486,780
108
951
1,012

Great answer. I would write just *... potentially n² such subsets...* (without the Θ). And use Θ instead of *O* in the last part of the answer. – aioobe Dec 08 '14 at 20:29
You are right. I've updated the output to only print the start and end index. – Gabriel Ivascu Dec 08 '14 at 20:32
@NPE I don't see how there are n² uninterrupted subsequences and not n*(n+1)/2. Just get a basic example such as {1, 2} -> {1}, {2}, {1,2}. Am I missing something? – Gabriel Ivascu Dec 08 '14 at 20:51
@GabrielIvascu: n*(n+1)/2=Θ(n²) - read up on the big-oh notation, e.g. http://stackoverflow.com/questions/3230122/big-oh-vs-big-theta – NPE Dec 08 '14 at 21:35
Usually we switch to [output sensitive](https://en.wikipedia.org/wiki/Output-sensitive_algorithm) bounds when the lower bound is of the form "the output is too large". For m results, the naive algorithm is Theta(n^2)-time, but the optimal algorithm (assuming constant-time hashing) is Theta(n + m)-time. – David Eisenstat Dec 08 '14 at 21:38
@NPE Yes, my bad, I failed to see you wrote Θ(n²) and not n². I am aware of the meaning of Θ but, for some reason, I was considering the exact number, don't know where I was thinking.. – Gabriel Ivascu Dec 08 '14 at 21:45

Find all uninterrupted subsequences whose sum is equal to zero

1 Answers1