Had time to finnally optimize it using itertools now.
from itertools import combinations
import time
list1 = range(10, 30)
int1 = 60
print 'List:', ', '.join([str(i) for i in list1])
list1 = list(set(list1))
list1 = [item for item in list1 if (item + min(list1)) <= int1]
print 'Clean List:', ', '.join([str(i) for i in list1])
subsets_list = []
def min_list(x, mlist):
m, rest = divmod(x, max(mlist))
if rest:
return m + 1
else:
return m
def max_list(x, mlist):
m, rest = divmod(x, min(mlist))
if not rest:
return m - 1
else:
return m
def subsets(nlist, wanted, min_list_size, max_list_size):
for s in range(min_list_size, max_list_size + 1):
rlist = [item for item in nlist if item >= (wanted / len(nlist))]
for item in combinations(rlist, s):
subsets_list.append(item)
t1 = time.clock()
subsets(list1, int1, min_list(int1, list1), max_list(int1, list1))
t2 = time.clock()
print 'Subsets took %0.3f ms to calculate %s subsets' % ((t2 - t1) * 1000.0, len(subsets_list))
valid_sums = [item for item in subsets_list if sum(item) == int1]
print '%s is the sum of %s subsets' % (int1, len(valid_sums))
for sums in valid_sums:
print '%s is the sum of %s' % (int1, ', '.join([str(i) for i in sums]))
Cheers and Happy coding