Subset Sum Recursively In Python

I will be happy to get some help. I have the following problem: I'm given a list of numbers seq and a target number and I need to write 2 things: A recursive solution that returns

Solution 1:

Just for reference, here's a solution using dynamic programming:

def positive_negative_sums(seq):
    P, N = 0, 0for e in seq:
        if e >= 0:
            P += e
        else:
            N += e
    return P, N

def subset_sum(seq, s=0):
    P, N = positive_negative_sums(seq)
    ifnot seq or s < N or s > P:
        return False
    n, m = len(seq), P - N + 1
    table = [[False] * m forx in xrange(n)]
    table[0][seq[0]] = True
    for i in xrange(1, n):
        for j in xrange(N, P+1):
            table[i][j] = seq[i] == j or table[i-1][j] or table[i-1][j-seq[i]]
    return table[n-1][s]

Solution 2:

This is how I'd write the subset_sum:

def subset_sum(seq, target):
    if target == 0:
        return True

    for i in range(len(seq)):
        if subset_sum(seq[:i] + seq[i+1:], target - seq[i]):
            return True
    return False

It worked on a couple of examples:

>>> subset_sum([-1,1,5,4], 0))
True>>> subset_sum([-1,1,5,4], 10)
True>>> subset_sum([-1,1,5,4], 4)
True>>> subset_sum([-1,1,5,4], -3)
False>>> subset_sum([-1,1,5,4], -4)
False

To be honest I wouldn't know how to memoize it.

Old Edit: I removed the solution with any() because after some tests I found out that to be slower!

Update: Just out of curiosity you could also use itertools.combinations:

from itertools import combinations

defcom_subset_sum(seq, target):
    if target == 0or target in seq:
        returnTruefor r inrange(2, len(seq)):
        for subset in combinations(seq, r):
            ifsum(subset) == target:
                returnTruereturnFalse

This can do better that the dynamic programming approach in some cases but in others it will hang (it's anyway better then the recursive approach).

Solution 3:

I have this modified code:

def subset_sum(seq, target):
    left, right = seq[0], seq[1:]return target in (0, left) or \
        (bool(right) and (subset_sum(right, target - left) or subset_sum(right, target)))

def subset_sum_mem(seq, target, mem=None):
    mem = mem or {}
    key = (len(seq), target)
    if key not in mem:
        left, right = seq[0], seq[1:]
        mem[key] = target in (0, left) or \
            (bool(right) and (subset_sum_mem(right, target - left, mem) or subset_sum_mem(right, target, mem)))
    return mem[key]

Can you provide some test cases this does not work for?