Python break/return a recursive function for sum of subsets

Question

I am trying to implement this function to find if the sums of any subsets equal a target value:

def subset_sum(numbers, target, partial=[]):
    s = sum(partial)

    # check if the partial sum is equals to target
    if s == target: 
        print "sum(%s)=%s" % (partial, target)
    if s >= target:
        return  # if we reach the number why bother to continue

    for i in range(len(numbers)):
        n = numbers[i]
        remaining = numbers[i+1:]
        subset_sum(remaining, target, partial + [n])

However, I would like the function to 'break' / return once there is an instance of the target being met, so that it doesn't continue to find more.

I've tried this, but it still continues:

def subset_sum(numbers, target, partial=[]):
    s = sum(partial)

    # check if the partial sum is equals to target
    if s == target: 
        print "sum(%s)=%s" % (partial, target)
        return   // should stop once reaches one instance
    if s >= target:
        return  # if we reach the number why bother to continue

    for i in range(len(numbers)):
        n = numbers[i]
        remaining = numbers[i+1:]
        subset_sum(remaining, target, partial + [n])

Mechanical: `partial=[]` means that `partial` is bound to a list instance created during the `def`. If you ever modify that list instance, bad things happen. You don't so that's OK, but I'd split this into the recursive code that has a `partial` and the outer call that doesn't, both for readability and for safety. Then use Reputation Farmer's method: have the recursive call tell you if it succeeded. — torek, Mar 11 '19 at 22:53
what is "numbers"? can you add, how you run the function with arguments. — Bhanu Tez, Mar 11 '19 at 22:54
Note also that your "s >= target" test assumes that no values in `numbers` are negative, but there's no documentation or test asserting that this is the case. — torek, Mar 11 '19 at 22:55
Note that return always returns to the previous call and in your recursive function call it returns to previous function call. If you want to exit the program itself you could try something similar to sys.exit See https://stackoverflow.com/questions/73663/terminating-a-python-script for options — ranjith, Mar 11 '19 at 23:07

Reputation Farmer · Answer 1 · 2019-03-11T22:56:51.247

Make subset_sum return bool: whether the subset was found. Check results of recursive calls.

def subset_sum(numbers, target, partial=[]):
    s = sum(partial)

    # check if the partial sum is equals to target
    if s == target: 
        print "sum(%s)=%s" % (partial, target)
        return True   # should stop once reaches one instance
    if s > target:
        return False # if we reach the number why bother to continue

    for i in range(len(numbers)):
        n = numbers[i]
        remaining = numbers[i+1:]
        if subset_sum(remaining, target, partial + [n]):
            return True
    return False

A better approach may be to return the answer (i.e. partial) or None.

Subsum44 · Accepted Answer · 2019-03-11T23:19:45.000

0

Edited: Missed the original algorithm, this should return the first valid list.

Try this:

def subset_sum(numbers, target, partial=[]): 
    s = sum(partial) # check if the partial sum is equals to target 
    if s >= target: # if we reach the number why bother to continue 
        return partial
    for i in range(len(numbers)):
        n = numbers[i]
        remaining = numbers[i+1:]
        results = subset_sum(remaining, target, partial + [n])
        if results:
            return results

edited Mar 11 '19 at 23:19

answered Mar 11 '19 at 22:57

Subsum44

36
6

But this isn't the algorithm and wouldn't yield required result/s – ranjith Mar 11 '19 at 23:04
You're right, I missed that. Updated so it returns the first list valid. – Subsum44 Mar 11 '19 at 23:20

Python break/return a recursive function for sum of subsets

2 Answers2