Is there an efficient way to find all integer tuples of length 10 that sum to 100-CodePudding

I am trying to find all tuples containing only positive integers (0 allowed) that add to 100. I have some constraints on the max values for each index. I have the list maxs that include these constraints

maxs = [3, 9, 14, 21, 21, 35, 31, 49, 42, 38]

So far I am simply running this 10 dimensional nested for loop

combinations = []
for s1 in range(maxs[0] 1):
    for s2 in range(maxs[1] 1):
        for s3 in range(maxs[2] 1):
            for s4 in range(maxs[3] 1):
                for s5 in range(maxs[4] 1):
                    for s6 in range(maxs[5] 1):
                        for s7 in range(maxs[6] 1):
                            for s8 in range(maxs[7] 1):
                                for s9 in range(maxs[8] 1):
                                    for s10 in range(maxs[9] 1):
                                        if s1  s2 s3 s4 s5 s6 s7 s8 s9 s10 == 100:
                                            combinations.append([s1,s2,s3,s4,s5,s6,s7,s8,s9,s10]

I know there are stictly less than 10^11 combinations if that helps at all. Maybe this problem is too large

Thanks

CodePudding user response：

Recursive approach. Example uses only three first entries. Acceleration is possible with early bad branch cutting - for example, when cursum exceeds target

maxs = [3, 9, 14, 21, 21, 35, 31, 49, 42, 38]

def sum100(n, target, maxs, level, cursum, curlist):
    if level == n:
        if cursum == target:
            print(curlist)
        return
    for i in range(maxs[level] 1):
        sum100(n, target, maxs, level   1, cursum   i, curlist   [i])

sum100(3, 15, maxs, 0, 0, [])

[0, 1, 14]
[0, 2, 13]
...
[1, 3, 11]
[1, 4, 10]
[1, 5, 9]
...
[3, 1, 11]
[3, 2, 10]
[3, 3, 9]

CodePudding user response：

This one is not the best performant one, but it is the easiest.

from itertools import combinations

maxs = [3, 9, 14, 21, 21, 35, 31, 49, 42, 38]

combination = [
    tuple(filter(lambda x: 0 <= x <= 100, item))
    for r in range(1, len(maxs))
    for item in combinations(maxs, r)
]
result = [item for item in combination if sum(item) == 100]

print(result)