Calculating if sum of subsets of a given list exists recursively

Question

I need to build a recursive function that receives an integer list (numbers) and a non-negative integer (target).

The function will look for any possible subset of the given list and if its values are added up and equal to the target, returns True.

def subset_sum(numbers, target):
    '''
    numbers - a list of positive integers
    target - a non-negative integer
    returns True if the list 'numbers' has a sub-list with sum 'target',
            False otherwise.
    '''

Side Note: [] is a subset of any given list (set)

Examples:

subset_sum([1,2,3,4], 8):

True

subset_sum([1,2,3,4], 11):

False

subset_sum([4,4,4], 05):

True

subset_sum([4,4,4], 11):

False

subset_sum([], 0):

True

Any help appreciated!

That i had failed to do so, and currently looking for help. – Menkes Nov 14 '15 at 07:10 — Menkes, Nov 14 '15 at 07:10

score 0 · Answer 1 · edited May 23 '17 at 12:15

0

This is a variant (sub-problem) on the subset sum problem which you can read about here:

https://en.wikipedia.org/wiki/Subset_sum_problem

There is a pseudocode algorithm outlined that solves the problem approximately in polynomial time for any integers (positive or negative). Interestingly enough this is posted on Stackoverflow and in python!

Fast solution to Subset sum

edited May 23 '17 at 12:15

Community

1
1

answered Nov 13 '15 at 11:45

user3261832

45
1
7

Calculating if sum of subsets of a given list exists recursively

1 Answers1