0

I want to write a python code that would print all the combination of given numbers that can sum up to a given number, like if you want to make 6 with 1, 2 and 3 the answer would be:

111111
11112
1113
123
...

there is going to be 24 combinations. is it possible?

Abolfazl Malekpour
  • 21
  • 3
  • 1
    Does this answer your question? [Finding all possible combinations of numbers to reach a given sum](https://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum) – Gino Mempin Nov 20 '21 at 04:45
  • Does this answer your question? [Find all combinations of a list of numbers with a given sum](https://stackoverflow.com/q/34517540/2745495) – Gino Mempin Nov 20 '21 at 04:47
  • Does this answer your question? [Find all combinations of a list of numbers with a given sum](https://stackoverflow.com/questions/34517540/find-all-combinations-of-a-list-of-numbers-with-a-given-sum) – Tyler V Nov 20 '21 at 05:07

1 Answers1

0

I am assuming that you are allowing for repetitions, unlike the suggested duplicate answers although really the idea is the same. You can use recursion as follows (or recursive generator instead):

def sum_to(num, parts):
    if num == 0:
        return [[]]
    return [[x, *lst] for x in parts if x <= num for lst in sum_to(num - x, parts)]

output = sum_to(6, [1, 2, 3])
print(len(output))
print(output)

Output:

24
[[1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 2], [1, 1, 1, 2, 1], [1, 1, 1, 3], [1, 1, 2, 1, 1], [1, 1, 2, 2], [1, 1, 3, 1], [1, 2, 1, 1, 1], [1, 2, 1, 2], [1, 2, 2, 1], [1, 2, 3], [1, 3, 1, 1], [1, 3, 2], [2, 1, 1, 1, 1], [2, 1, 1, 2], [2, 1, 2, 1], [2, 1, 3], [2, 2, 1, 1], [2, 2, 2], [2, 3, 1], [3, 1, 1, 1], [3, 1, 2], [3, 2, 1], [3, 3]]
j1-lee
  • 13,764
  • 3
  • 14
  • 26