Display subset in recursive algorithm for subset sum

Question

I have the following algorithm that solves the subset sum problem recursively:

def findSubset(alist, targ, i, sumsofar):
    if sumsofar == targ:
        return True
    if i == len(alist):
        return False
    inc = findSubset(alist, targ, i+1, sumsofar+alist[i])
    noninc = findSubset(alist, targ, i+1, sumsofar)
    return inc or noninc

The algorithm works fine, but it only gives a boolean answer. So if I call it as so:

alist = [4, 6, 21, 29, 37, 50]
findSubset(alist, 76, 0, 0)
>>> True

But I would like it to return [4, 6, 29, 37]

Here is my attempt at altering the algorithm:

def findSubset(alist, targ, i, sumsofar, new):
    if sumsofar == targ:
        return new
    if i == len(alist):
        return []
    inc = findSubset(alist, targ, i+1, sumsofar+alist[i], new.append(alist[i]))
    noninc = findSubset(alist, targ, i+1, sumsofar, new)
    return inc or noninc

Where it is used as so:

alist = [4, 6, 21, 29, 37, 50]
findSubset(alist, 76, 0, 0, [])
>>>AttributeError: 'NoneType' object has no attribute 'append'

What must I do to make it work, is it even possible?

change return inc or nonionic to return inc if inc else noninc ? — Moraes
– Moraes, Commented Oct 31, 2015 at 23:46

Hengfeng Li · Accepted Answer · 2015-11-01 00:03:26Z

1

My following code works:

def findSubset(alist, targ, i, sumsofar, listsofar):
    if sumsofar == targ:
        return True, listsofar
    if i == len(alist):
        return False, listsofar
    inc, inclistsofar = findSubset(alist, targ, i+1, sumsofar+alist[i], listsofar + [alist[i]])
    noninc, noninclistsofar = findSubset(alist, targ, i+1, sumsofar, listsofar)

    if inc:
        return inc, inclistsofar
    else:
        return noninc, noninclistsofar

alist = [4, 6, 21, 29, 37, 50]
print findSubset(alist, 76, 0, 0, [])

list.append() is an in-place operation. It returns None type, but you need to pass a list as an argument.

answered Nov 1, 2015 at 0:03

Hengfeng Li

3911 gold badge6 silver badges12 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Mike Müller · Accepted Answer · 2015-11-01 00:59:35Z

0

Improvement of the solution by Hengfeng Li. Use default parameters to allow a nicer call without the zeros and the empty list find_subset(alist, 76):

def find_subset(alist, targ, i=0, sumsofar=0, listsofar=None):
    if listsofar is None:
        listsofar = []
    if sumsofar == targ:
        return True, listsofar
    if i == len(alist):
        return False, listsofar
    inc, inclistsofar = find_subset(alist, targ, i+1, sumsofar + alist[i], listsofar + [alist[i]])
    noninc, noninclistsofar = find_subset(alist, targ, i+1, sumsofar, listsofar)

    if inc:
        return inc, inclistsofar
    else:
        return noninc, noninclistsofar

alist = [4, 6, 21, 29, 37, 50]
print(find_subset(alist, 76))

UPDATE

Further improvements based on comment from Blckknght:

def find_subset(alist, targ, i=0, sumsofar=0, listsofar=None):
    if listsofar is None:
        listsofar = []
    if sumsofar == targ:
        return listsofar
    if i == len(alist):
        return None
    inclistsofar = find_subset(alist, targ, i+1, sumsofar + alist[i], 
                               listsofar + [alist[i]])
    if inclistsofar:
        return inclistsofar
    else:
        noninclistsofar = find_subset(alist, targ, i+1, sumsofar, listsofar)
        return noninclistsofar

alist = [4, 6, 21, 29, 37, 50]
print(find_subset(alist, 76))
print(find_subset(alist, 100))
print(find_subset(alist, 1000))
print(find_subset(alist, 4))
print(find_subset(alist, 17))

Output:

[4, 6, 29, 37]
[21, 29, 50]
None
[4]
None

edited Nov 1, 2015 at 0:59

answered Nov 1, 2015 at 0:35

Mike Müller

86k21 gold badges174 silver badges165 bronze badges

2 Comments

Blckknght Over a year ago

A further improvement would be to get rid of the inc and noninc booleans and return None when there's no valid sum. You can probably also greatly improve performance by short circuting and not making the the second recursion if the first one found a result (inclistsofar = find_subset(...); if inclistsofar is not None: return inclistsofar).

Mike Müller Over a year ago

@Blckknght Thanks for the hint. Looks better now.

Collectives™ on Stack Overflow

Display subset in recursive algorithm for subset sum

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related