Subsequence sum

Question

Given an array of integers eg [1, 2, -3, 1] find whether there is a sub-sequence that sums to 0 and return it (eg [1, 2, -3] or [2, -3, 1]).
Checking every sub-sequence is O(n^2) which is too inefficient. Any idea for improvements?

Answer 1

Make a new array with each element equal to the sum of the previous elements plus that one.

Input:

1  4 -3 -4  6  -7  8 -5 

Becomes:

1  5  2  -2  4  -3  5  0    ^                ^ 

Then look for elements that match in the resulting array.

Since these represent locations where the overall change in the function is zero, you will find that if their position is i and k then the subsequence (i+1, k) is a zero-sum subsequence. (In this case, [2:6]).

Additionally, any zeros in the table indicate that the subsequence (0, k) is a zero-sum subsequence. For the lookup, a hash table or other fast collision locator makes this O(N) to perform.

Answer 2

Do a running sum, storing sum values in a hash table along with array index

If you ever get a sum value you’ve already seen, return 1+the index in the hash table, and the current index. This solution is O(n) time complexity.

No need for a new array. Space complexity is O(N) because of the hash.

---

A Python implementation:

input = [1, 4, -3, -4, 6, -7, 8, -5] map = {} sum = 0 for i in range(len(input)):     sum += input[i]     if sum in map:         print map[sum][0] + 1, "to", i     map[sum] = (i, sum) 

Notice that repeated subsequences are not shown, example: If (1 to 2) is a subsequence and (3 to 4), (1 to 4) won't be shown. You can achieve this behavior by storing lists in each position of the map:

for x in map[sum]:     print x[0]+1, "to", i map[sum].append((i, sum))