Python program to find set of elements in a list to sum up to a certain number


import pdb

def checker(list, i, mem, S ):
if i >= len(list): return 1 if S == 0 else 0
if (i, S) not in mem: # Check if value has not been calculated earlier.
count = checker(list, i + 1, mem, S )
count += checker(list, i + 1, mem, S - list[i])
mem[(i, S)] = count # memorize calculated result so far.
return mem[(i, S)]

def finder(list, mem,S ):
sublist = []
for i, x in enumerate(list):
# Check if there is still a solution if we include list[i]
if checker(list, i + 1, mem,S - x) > 0:
sublist.append(x)
S -= x
return sublist

def main():
list = [6,2,3,1,4,5,7]
sum = 9 # Suppose we are looking for sum=9, user can look as per their wish
mem = dict()
#pdb.set_trace()
if checker(list, 0, mem, sum ) == 0:
print("Don't find valid sublist.")
else:
print(finder(list, mem, sum ))

if __name__ == "__main__":
main()

Advertisements
Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: