CareerCup

we can modify the key_dict as key: [positions], it still could be O(n)

DP, O(n), with python

def output(original, pre):

    if len(original) == 0:
        print pre
        return
    if len(original) == 1:
        print pre + chr(96 + int(original))
        return


    if int(original[0:2]) < 27:
        new_chr = chr(96 + int(original[0:2]))
        output(original[2:], pre + new_chr)
    new_chr = chr(96 + int(original[0:1]))
    output(original[1:], pre + new_chr)





if __name__ == '__main__':
    output('1123', '')

It could be done with O(n)

1) run cumulate sum on the original array
2) append [0] in font of this cum_sum_array
3) check if two item in this cum_sum_array are same (for requirement sum==0, this could be done in O(n))

Totally time spend is O(2n) = O(n)

I'm using python:

import numpy as np
def get_sum(array):
    cumsum_array = [0] + np.cumsum(array).tolist()
    key_dict = {}
    for index, cum_sum in enumerate(cumsum_array):
        if cum_sum not in key_dict:
            key_dict[cum_sum] = index
            continue
        print array[key_dict[cum_sum]: index]


if __name__ == '__main__':
    
    array = [-1, -3, 4, 5, -2, -4, 6]
    get_sum(array)

output:

[-1, -3, 4]
[-3, 4, 5, -2, -4]
[-2, -4, 6]