5

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:

  1. A recursive solution that returns True if there is a sum of a subsequence that equals the target number and False otherwise. example:

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

  2. Secondly, I need to write a solution using what I wrote in the previous solution but now with memoization that uses a dictionary in which the keys are tuples: (len(seq),target)

For number 1 this is what I got to so far:

def subset_sum(seq, target):
    if target == 0: 
        return True
    if seq[0] == target:
        return True
    if len(seq) > 1:
        return subset_sum(seq[1:],target-seq[0]) or subset_sum(seq[1:],target)
    return False

Not sure I got it right so if I could get some input I will be grateful.

For number 2:

def subset_sum_mem(seq, target, mem=None ):
    if not mem:
        mem = {}
    key=(len(seq),target)
    if key not in mem:
        if target == 0 or seq[0]==target:
            mem[key] = True
        if len(seq)>1:
            mem[key] = subset_sum_mem(seq[1:],target-seq[0],mem) or subset_sum_mem(seq[1:],target,mem)
        mem[key] = False

    return mem[key]

I can't get the memoization to give me the correct answer so I'd be glad for some guidance here.

Thanks for anyone willing to help!

Improve this question
3
  • 2
    Any reason you're not just using @memoize? Commented Jan 26, 2012 at 20:01
  • 2
    Probably because it's homework ;) Commented Jan 26, 2012 at 20:08
  • 4
    Please tag as homework if this is in fact homework. People will still help. It is good form and can help people understand where you are coming from. Commented Jan 26, 2012 at 20:11

3 Answers 3

Reset to default
1

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

def positive_negative_sums(seq):
    P, N = 0, 0
    for 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)
    if not seq or s < N or s > P:
        return False
    n, m = len(seq), P - N + 1
    table = [[False] * m for x 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]
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Very nice. Alternative: def positive_negative_sums(seq): return sum(e for e in seq if e >= 0), sum(e for e in seq if e < 0)
0

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

def com_subset_sum(seq, target):
    if target == 0 or target in seq:
        return True

    for r in range(2, len(seq)):
        for subset in combinations(seq, r):
            if sum(subset) == target:
                return True
    return False

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).

Improve this answer

3 Comments

subset_sum = lambda seq, target: (target == 0) or any(subset_sum(seq[:i] + seq[i+1:], target - v) for i, v in enumerate(seq)) for us masochists ;) Memoization is actually trivial dictionary lookup in this case. Nice solution!
Or: ` return any(subset_sum(seq[:i] + seq[i+1:], target - seq[i]) for i in range(len(seq)))`
@user1123417: You're welcome, if you find it useful you can up-vote it (as a reward for our effort), and if it was the most useful one in solving your problem you can also accept it (green arrow on the left) :)
0

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?

Improve this answer

5 Comments

it works great! thank you very much. in order to understand the solution in depth can you please explain what the return line does? return target in (0, left) or \ (bool(right) and (subset_sum(right, target - left) or subset_sum(right, target)))
If this is homework, then you should figure out how that works -- and how it is identical to your original code.
The only thing i don't understand is what bool(right) gives to the solution. Can you explain?
Hmmmm. I was getting [] as a return value at some point in my experimentation, so I cast right to a bool. Now I can't come up with a case where it is needed.
Change bool(right) to right and try: subset_sum([2], 1) and subset_sum_mem([2], 1).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.