pythonalgorithmpython-3.xcombinationssubset-sum

Find all combinations of a list of numbers with a given sum


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]]


Solution

  • 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.