Найти все комбинации номеров чисел с заданной суммой

Question

У меня есть список номеров, например.

numbers = [1, 2, 3, 7, 7, 9, 10] 

Как вы можете видеть, цифры могут появляться более одного раза в этом списке.

Мне нужно получить все комбинации этих чисел, которые имеют заданную сумму, например. 10.

Элементы в комбинациях могут не повторяться, но каждый элемент в numbers должен обрабатываться однозначно, что означает, например, два 7 в списке представляют разные элементы с одинаковым значением.

Заказ не имеет значения, так что [1, 9] и [9, 1] такие же комбинации.

Ограничений на длину для комбинаций не существует, [10] действителен как [1, 2, 7].

Как создать список всех комбинаций, соответствующих вышеуказанным критериям?

В этом примере было бы [[1,2,7], [1,2,7], [1,9], [3,7], [3,7], [10]]

Answer 1

Вы можете использовать itertools, чтобы перебирать все комбинации всевозможных размеров, и отфильтровать все, что не суммируется до 10:

import itertools 
numbers = [1, 2, 3, 7, 7, 9, 10] 
result = [seq for i in range(len(numbers), 0, -1) for seq in itertools.combinations(numbers, i) if sum(seq) == 10] 
print result 

Результат:

[(1, 2, 7), (1, 2, 7), (1, 9), (3, 7), (3, 7), (10,)] 

к сожалению, это что-то вроде O (2^N) сложности, поэтому он не подходит для ввода списков больше, чем, скажем, 20 е lements.

Answer 2

Этот вопрос задан раньше, см. @msalvadores ответ here. Я обновил код питона данный работать в Python 3:

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

    # check if the partial sum is equals to target 
    if s == target: 
     print("sum(%s)=%s" % (partial, target)) 
    if s >= target: 
     return # if we reach the number why bother to continue 

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


if __name__ == "__main__": 
    subset_sum([3, 3, 9, 8, 4, 5, 7, 10], 15) 

    # Outputs: 
    # sum([3, 8, 4])=15 
    # sum([3, 5, 7])=15 
    # sum([8, 7])=15 
    # sum([5, 10])=15 

Answer 3

solution @kgoodrick offered является большим, но я думаю, что это более полезно в качестве генератора:

def subset_sum(numbers, target, partial=[], partial_sum=0): 
    if partial_sum == target: 
     yield partial 
    if partial_sum >= target: 
     return 
    for i, n in enumerate(numbers): 
     remaining = numbers[i + 1:] 
     yield from subset_sum(remaining, target, partial + [n], partial_sum + n) 

list(subset_sum([1, 2, 3, 7, 7, 9, 10], 10)) дает [[1, 2, 7], [1, 2, 7], [1, 9], [3, 7], [3, 7], [10]].