Genere todas las listas posibles de longitud N que sumen S en Python

Estoy tratando de generar todas las listas posibles de Longitud N que sumn a S. He escrito algún código para hacerlo, pero en algo grande (en particular, quiero N = 5, S = 100), corro en la memoria errores de desbordamiento.

Estoy buscando una mejor solución al problema o una forma de mejorar mi código para poder ejecutarlo en N = 5, S = 100. Estos dos progtwigs siguientes trabajan en tándem para crear todas las combinaciones de números posibles en listas anidadas y luego volver a trabajar para que tengan el formato correcto. Algunas muestras de salida se reproducen a continuación.

Sé que mi código no es el mejor. Soy ingeniero de oficio (lo sé, lo sé), por lo que la encoding no es exactamente mi fuerte. Aprecio cualquier ayuda que pueda proporcionar.

EDIT: sólo quería aclarar algunas cosas. Primero, está bien tener cero en las listas, las listas pueden contener múltiplos del mismo número, y el orden de los números en las listas es importante.

def nToSum(N,S): ''' Creates a nested list of all possible lists of length N that sum to S''' if N >> nToSum(3,3) [[0, [[0, [3]], [1, [2]], [2, [1]], [3, [0]]]], [1, [[0, [2]], [1, [1]], [2, [0]]]], [2, [[0, [1]], [1, [0]]]], [3, [[0, [0]]]]] >>> compress([],nToSum(3,3)) [[0, 0, 3], [0, 1, 2], [0, 2, 1], [0, 3, 0], [1, 0, 2], [1, 1, 1], [1, 2, 0], [2, 0, 1], [2, 1, 0], [3, 0, 0]] 

    Usar un generador ahorra en la memoria (use xrange lugar de range si usa Python 2). Esto es lo que se me ocurrió. Es muy similar a su nToSum sin la necesidad de compress .

     def f(length,total_sum): if length == 1: yield (total_sum,) else: for value in range(total_sum + 1): for permutation in sums(length - 1,total_sum - value): yield (value,) + permutation L = list(f(5,100)) print('total permutations:',len(L)) # First and last 10 of list for i in L[:10] + L[-10:]: print(i) 

    Salida

     total permutations: 4598126 (0, 0, 0, 0, 100) (0, 0, 0, 1, 99) (0, 0, 0, 2, 98) (0, 0, 0, 3, 97) (0, 0, 0, 4, 96) (0, 0, 0, 5, 95) (0, 0, 0, 6, 94) (0, 0, 0, 7, 93) (0, 0, 0, 8, 92) (0, 0, 0, 9, 91) (98, 0, 2, 0, 0) (98, 1, 0, 0, 1) (98, 1, 0, 1, 0) (98, 1, 1, 0, 0) (98, 2, 0, 0, 0) (99, 0, 0, 0, 1) (99, 0, 0, 1, 0) (99, 0, 1, 0, 0) (99, 1, 0, 0, 0) (100, 0, 0, 0, 0)