【数组】--N-Sum问题

def EnumNumber(arr, x, i, residue):
    if i >= len(arr):
        return
    if arr[i] == residue:
        x[i] = 1
        print x
        x[i] = 0
        # return

    x[i] = 1
    EnumNumber(arr, x, i+1, residue-arr[i])
    x[i] = 0
    EnumNumber(arr, x, i+1, residue)


def FindNumber(arr, x, i, residue, target):
    if i >= len(arr):
        return
    if arr[i] == target:
        x[i] = 1
        print x
        x[i] = 0

    if (residue >= target) and (arr[i] <= target):
        x[i] = 1
        FindNumber(arr, x, i+1, residue-arr[i], target-arr[i])
        x[i] = 0

    if ((residue-arr[i]) >= target):
        x[i] = 0
        FindNumber(arr, x, i+1, residue-arr[i], target)


def FindNumberNeg(arr, x, i, neg, postive, target):
    if i >= len(arr):
        return
    if arr[i] == target:
        x[i] = 1
        print x
        x[i] = 0

    if arr[i] >= 0:
        if (postive >= target) and (arr[i] <= target):
            x[i] = 1
            FindNumberNeg(arr, x, i+1, neg, postive-arr[i], target-arr[i])
            x[i] = 0

        if ((postive-arr[i]) >= target):
            x[i] = 0
            FindNumberNeg(arr, x, i+1, neg, postive-arr[i], target)
    else:
        if (arr[i]+postive) >= target:
            x[i] = 1
            FindNumberNeg(arr, x, i+1, neg-arr[i], postive, target-arr[i])
            x[i] = 0
        # else:
        # if (neg <= target) and (postive >= target): 
        if postive >= target:
            x[i] = 0
            FindNumberNeg(arr, x, i+1, neg-arr[i], postive, target)


def nsum(arr, target):
    x = [0]*len(arr)
    # EnumNumber(arr, x, 0, target)
    # FindNumber(arr, x, 0, sum(arr), target)
    postive = neg = 0
    for i in arr:
        if i >= 0:
            postive += i
        else:
            neg += i
    print postive, neg
    FindNumberNeg(arr, x, 0, neg, postive, target)

if __name__ == "__main__":
# arr = [1, 2, 3, 4, 5, 0]
    arr = [-3, -5, -2, 4, 2, 1, 3]
    nsum(arr, 5)