I have a list of numbers, e.g.
numbers = [1, 2, 3, 7, 7, 9, 10]
As you can see, numbers may appear more than once in this list.
I need to get all combinations of these numbers that have a given sum, e.g. 10.
The items in the combinations may not be repeated, but each item in numbers has to be treated uniquely, that means e.g. the two 7 in the list represent different items with the same value.
The order is unimportant, so that [1, 9] and [9, 1] are the same combination.
There are no length restrictions for the combinations, [10] is as valid as [1, 2, 7].
How can I create a list of all combinations meeting the criteria above?
In this example, it would be [[1,2,7], [1,2,7], [1,9], [3,7], [3,7], [10]]
You could use itertools to iterate through every combination of every possible size, and filter out everything that doesn't sum to 10:
import itertools
numbers = [1, 2, 3, 7, 7, 9, 10]
target = 10
result = [seq for i in range(len(numbers), 0, -1)
for seq in itertools.combinations(numbers, i)
if sum(seq) == target]
print(result)
Result:
[(1, 2, 7), (1, 2, 7), (1, 9), (3, 7), (3, 7), (10,)]
Unfortunately this is something like O(2^N) complexity, so it isn't suitable for input lists larger than, say, 20 elements.