For an arbitrary sequence of integers, identify all sub-sequences with a sum of 0.

sub_seq.py

"""

For an arbitrary sequence of integers, identify all sub-sequences
with a sum of 0.

"""
import sys

def build_tree(ints, x):
    """
    Build a recursive sum tree based on the passed list.
    """
    output = []
    for x in range(x, len(ints) - 1, 2):
        y = ints[x]
        z = ints[x + 1]
        newNode = (y[0] + z[0],
                   y[1],
                   z[2])
        output.append(newNode)

    if len(ints) % 2 == 1:
        output.append(ints[len(ints) - 1])

    if len(output) > 1:
        output += build_tree(output, 0)

    return output

def get_zero_sums(tree, ints):
    """
    Reduce the tree down, accomodating edge cases.
    """
    zero_sums = []
    tree = reversed(tree)
    for node in tree:
        if node[0] == 0:
            zero_sums.append(node)
        else:
            if len(ints) - 1 > node[2]:
                new_value = node[0] + ints[node[2] + 1][0]
                if new_value == 0:
                    new_node = (new_value,
                                node[1],
                                node[2] + 1)
                    zero_sums.append(new_node)
            if node[1] > 0:
                new_value = node[0] + ints[node[1] - 1][0]
                if new_value == 0:
                    new_node = (new_value,
                                node[1] - 1,
                                node[2])
                    zero_sums.append(new_node)
    return set(zero_sums)

def start(values):
    """
    Take the list of values and create two sum trees, one starting at
    element 0 and the next element 1.

    """
    ints = []
    x = 0
    for value in values:
        ints.append((value, x, x))
        x += 1
    output_even = build_tree(ints, 0)
    output_odd = build_tree(ints, 1)

    zero_sums = get_zero_sums(output_even, ints).union(get_zero_sums(output_odd, ints))
    for _, start, end in zero_sums:
        print("Found seq: " + ", ".join([str(x) for x in values[start:end+1]]))

if __name__ == "__main__":
    if len(sys.argv) < 2:
        print('Usage python test.py 2 1 3 -4 -1 -1 2')
        sys.exit()
    values = [int(x) for x in sys.argv[1:]]
    start(values)