A sum is given, for example 25, and numbers are given, for example 2, 5, 10 You need to find all the combinations for choosing this amount. That is, the program should output 5 + 5 + 5 + 5 + 5, 5 + 5 + 5 + 10, 5 + 10 + 10, 2 + 2 + 2 + 2 + 2 + 10 + 5 and so on.
What algorithms / methods / libraries do you recommend using?
You can use itertools to get all the combinations, then keep only those that sum up to 25. I used with_replacement because the same value can come twice. Also, I used the flooring division because no number can come more often than the smallest one.
from itertools import combinations_with_replacement
candidates = list()
for i in range(25//2): # floor division of largest by smallest
candidates.extend(list(combinations_with_replacement([2, 5, 10], i)))
positive_cases = [i for i in candidates if sum(i) == 25]
[(5, 10, 10), (5, 5, 5, 10),
(5, 5, 5, 5, 5), (2, 2, 2, 2, 2, 5, 10),
(2, 2, 2, 2, 2, 5, 5, 5),
(2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 5)]
combinations_with_replacement instead of combinations. There is a distinct difference between the two.
yield statement instead so it's not all in memoryThe number is the coefficient of x^25 in 1/((1-x^2)(1-x^5)(1-x^10))
So, sympy is your friend.
You can also do this using dynamic programming.
