from itertools import chain, combinations
MAX_COMBO = 7
def powerset(iterable):
s = list(iterable)
return chain.from_iterable(combinations(s, r) for r in range(MAX_COMBO+1))
nums = [409,
411,
464,
475,
512,
522,
558,
580,
674,
693,
725,
728,
740,
749,
761,
773,
787,
798,
894,
929,
973,
992,
1146,
1171,
1264,
1292,
1307,
1539,
]
inputSum = 2000
nums_filter = set([n for n in nums if n <= inputSum])
print("nums : {}, filtered : {}".format(len(nums), len(nums_filter)))
for i, combo in enumerate(powerset(nums_filter), 1):
sum = 0
for num in combo:
sum += int(num)
if sum == inputSum:
print(combo)
ZnJvbSBpdGVydG9vbHMgaW1wb3J0IGNoYWluLCBjb21iaW5hdGlvbnMKCk1BWF9DT01CTyA9IDcKCgpkZWYgcG93ZXJzZXQoaXRlcmFibGUpOgogICAgcyA9IGxpc3QoaXRlcmFibGUpCiAgICByZXR1cm4gY2hhaW4uZnJvbV9pdGVyYWJsZShjb21iaW5hdGlvbnMocywgcikgZm9yIHIgaW4gcmFuZ2UoTUFYX0NPTUJPKzEpKQoKCm51bXMgPSBbNDA5LAo0MTEsCjQ2NCwKNDc1LAo1MTIsCjUyMiwKNTU4LAo1ODAsCjY3NCwKNjkzLAo3MjUsCjcyOCwKNzQwLAo3NDksCjc2MSwKNzczLAo3ODcsCjc5OCwKODk0LAo5MjksCjk3MywKOTkyLAoxMTQ2LAoxMTcxLAoxMjY0LAoxMjkyLAoxMzA3LAoxNTM5LApdCgppbnB1dFN1bSA9IDIwMDAKCm51bXNfZmlsdGVyID0gc2V0KFtuIGZvciBuIGluIG51bXMgaWYgbiA8PSBpbnB1dFN1bV0pCnByaW50KCJudW1zIDoge30sIGZpbHRlcmVkIDoge30iLmZvcm1hdChsZW4obnVtcyksIGxlbihudW1zX2ZpbHRlcikpKQpmb3IgaSwgY29tYm8gaW4gZW51bWVyYXRlKHBvd2Vyc2V0KG51bXNfZmlsdGVyKSwgMSk6CiAgICBzdW0gPSAwCiAgICBmb3IgbnVtIGluIGNvbWJvOgogICAgICAgIHN1bSArPSBpbnQobnVtKQogICAgaWYgc3VtID09IGlucHV0U3VtOgogICAgICAgIHByaW50KGNvbWJvKQ==