How to find all possibilities of integers that add up to 15 in Python? [closed]-CodePudding

I want to find all of the possibilities of three integers that add up to 15 in Python. I heard of itertools before, but thoses are for permutations. What should I do?

CodePudding user response：

If what you mean are positive integers, a naive solution is get all possible combinations of 3 numbers from 0 to 15 (repeating numbers allowed). Then filter only those where the sum is 15.

from itertools import combinations_with_replacement

target_sum = 15

addends = list(range(0, target_sum   1))
possible_combs = list(
    filter(
        lambda comb: sum(comb) == target_sum,
        combinations_with_replacement(addends, 3)
    )
)

print(possible_combs)

Output:

[(0, 0, 15), (0, 1, 14), (0, 2, 13), (0, 3, 12), (0, 4, 11), (0, 5, 10), (0, 6, 9), (0, 7, 8), (1, 1, 13), (1, 2, 12), (1, 3, 11), (1, 4, 10), (1, 5, 9), (1, 6, 8), (1, 7, 7), (2, 2, 11), (2, 3, 10), (2, 4, 9), (2, 5, 8), (2, 6, 7), (3, 3, 9), (3, 4, 8), (3, 5, 7), (3, 6, 6), (4, 4, 7), (4, 5, 6), (5, 5, 5)]

As you might guess, this isn't optimal if the target sum is a high number as the number of combinations to check would grow exponentially.

CodePudding user response：

I think itertools will be the best thing for solving this type of problem as they provide us a great functionality. As this type of problems require permutations only. Here is a sample code for your reference:

def subset_sum(numbers, target, partial=[]):
s = sum(partial)

# check if the partial sum is equals to target
if s == target:
    if len(partial) == 3: #as we want 3 integers only
                          #remove if you want all
        print("sum(%s)=%s" % (partial, target))
        if s >= target:
    return  # break as we reached the number

    for i in range(len(numbers)):
        n = numbers[i]
        remaining = numbers[i 1:]
        subset_sum(remaining, target, partial   [n]) 

if __name__ == "__main__"
subset_sum([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15],15)

#Outputs

sum([1, 2, 12])=15
sum([1, 3, 11])=15
sum([1, 4, 10])=15
sum([1, 5, 9])=15
sum([1, 6, 8])=15
sum([2, 3, 10])=15
sum([2, 4, 9])=15
sum([2, 5, 8])=15
sum([2, 6, 7])=15
sum([3, 4, 8])=15
sum([3, 5, 7])=15
sum([4, 5, 6])=15