target_sum_sub_array.py

"""
    Given a target, find the list of numbers that sum to the target
"""
def targetSum(a,k):
    s={0:[]}
    res = []
    for x in a:
        ns=dict(s)
        for j in s:
            if j+x == k:
                res.append(s[j]+[x])
            ns[j+x]=s[j]+[x]
        s=ns
    return res
print targetSum([-3,-5,9,12,0,3,2], 3)