Encuentra todas las combinaciones de una lista de números con una sum dada

Tengo una lista de números, por ejemplo

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

Como puede ver, los números pueden aparecer más de una vez en esta lista.

Necesito obtener todas las combinaciones de estos números que tienen una sum dada, por ejemplo, 10 .

Es posible que los elementos de las combinaciones no se repitan, pero cada elemento en numbers debe tratarse de forma única, lo que significa que, por ejemplo, los dos 7 en la lista representan elementos diferentes con el mismo valor.

El orden no es importante, por lo que [1, 9] y [9, 1] son la misma combinación.

No hay restricciones de longitud para las combinaciones, [10] es tan válido como [1, 2, 7] .

¿Cómo puedo crear una lista de todas las combinaciones que cumplan los criterios anteriores?

En este ejemplo, sería [[1,2,7], [1,2,7], [1,9], [3,7], [3,7], [10]]

Podría usar itertools para recorrer cada combinación de cada tamaño posible y filtrar todo lo que no sume 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 

Resultado:

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

Desafortunadamente, esto es algo así como la complejidad de O (2 ^ N), por lo que no es adecuado para listas de entrada más grandes que, digamos, 20 elementos.

La solución que ofreció @kgoodrick es excelente, pero creo que es más útil como generador:

 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)) produce [[1, 2, 7], [1, 2, 7], [1, 9], [3, 7], [3, 7], [10]] .

Esta pregunta se ha hecho antes, vea la respuesta de @msalvadores aquí . Actualicé el código de Python dado para ejecutarse en 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