Python Subset Sum

Question

I am trying to write a function that will not only determine whether the sum of a subset of a set adds to a desired target number, but also to print the subset that is the solution.

Here is my code for finding whether a subset exists:

def subsetsum(array,num):

    if num == 0 or num < 1:
        return False
    elif len(array) == 0:
        return False
    else:
        if array[0] == num:
            return True
        else:
            return subsetsum(array[1:],(num - array[0])) or subsetsum(array[1:],num)

How can I modify this to record the subset itself so that I can print it? Thanks in advance!

Answer 1

Based on your solution:

def subsetsum(array,num):

    if num == 0 or num < 1:
        return None
    elif len(array) == 0:
        return None
    else:
        if array[0] == num:
            return [array[0]]
        else:
            with_v = subsetsum(array[1:],(num - array[0])) 
            if with_v:
                return [array[0]] + with_v
            else:
                return subsetsum(array[1:],num)

Answer 2

Slightly modified version of Samy's answer to print all possible combinations.

def subset(array, num):
    result = []
    def find(arr, num, path=()):
        if not arr:
            return
        if arr[0] == num:
            result.append(path + (arr[0],))
        else:
            find(arr[1:], num - arr[0], path + (arr[0],))
            find(arr[1:], num, path)
    find(array, num)
    return result

Answer 3

You could change your approach to do that more easily, something like:

def subsetsum(array, num):
    if sum(array) == num:
        return array
    if len(array) > 1:
        for subset in (array[:-1], array[1:]):
            result = subsetsum(subset, num)
            if result is not None:
                return result

This will return either a valid subset or None.

Answer 4

Thought I'll throw another solution into the mix.

We can map each selection of a subset of the list to a (0-padded) binary number, where a 0 means not taking the member in the corresponsing position in the list, and 1 means taking it.

So masking [1, 2, 3, 4] with 0101 creates the sub-list [2, 4].

So, by generating all 0-padded binary numbers in the range between 0 and 2^LENGTH_OF_LIST, we can iterate all selections. If we use these sub-list selections as masks and sum the selection - we can know the answer.

This is how it's done:

#!/usr/bin/env python

# use a binary number (represented as string) as a mask
def mask(lst, m):
    # pad number to create a valid selection mask 
    # according to definition in the solution laid out 
    m = m.zfill(len(lst))
    return map(lambda x: x[0], filter(lambda x: x[1] != '0', zip(lst, m)))

def subset_sum(lst, target):
    # there are 2^n binary numbers with length of the original list
    for i in xrange(2**len(lst)):
        # create the pick corresponsing to current number
        pick = mask(lst, bin(i)[2:])
        if sum(pick) == target:
            return pick
    return False


print subset_sum([1,2,3,4,5], 7)

Output:

[3, 4]

To return all possibilities we can use a generator instead (the only changes are in subset_sum, using yield instead of return and removing return False guard):

#!/usr/bin/env python

# use a binary number (represented as string) as a mask
def mask(lst, m):
    # pad number to create a valid selection mask 
    # according to definition in the solution laid out 
    m = m.zfill(len(lst))
    return map(lambda x: x[0], filter(lambda x: x[1] != '0', zip(lst, m)))

def subset_sum(lst, target):
    # there are 2^n binary numbers with length of the original list
    for i in xrange(2**len(lst)):
        # create the pick corresponsing to current number
        pick = mask(lst, bin(i)[2:])
        if sum(pick) == target:
            yield pick

# use 'list' to unpack the generator
print list(subset_sum([1,2,3,4,5], 7))

Output:

[[3, 4], [2, 5], [1, 2, 4]]

---

Note: While not padding the mask with zeros may work as well, as it will simply select members of the original list in a reverse order - I haven't checked it and didn't use it.

I didn't use it since it's less obvious (to me) what's going on with such trenary-like mask (1, 0 or nothing) and I rather have everything well defined.