Generate all possible lists of length N that sum to S in Python

Question

I'm trying to generate all possible lists of Length N that sum to S. I've written some code to do so, but on anything large (in particular, I want N=5, S=100), I run into memory overflow errors.

I'm looking for either a better solution to the problem, or a way to improve my code so I can run it on N=5, S=100. These two programs below work in tandem to create all the possible number combinations in nested lists, and then re-work them to be the right format. Some sample output is reproduced below.

I know my code isn't the best. I'm an engineer by trade (I know, I know), so coding isn't exactly my forte. I appreciate any help you can provide.

EDIT: I just wanted to clarify a few thing. First, it's ok to have zero in the lists, the lists can contain multiples of the same number, and the order of the numbers in the lists matters.

def nToSum(N,S):
    ''' Creates a nested list of all possible lists of length N that sum to S'''
    if N <= 1: #base case
        return [S]
    else:
        L = []
        for x in range(S+1):   #create a sub-list for each possible entry of 0 to S 
            L += [[x,nToSum(N-1,S-x)]]  #create a sub-list for this value recursively
        return L

def compress(n=[],L): #designed to take in a list generated by nToSum
    '''takes the input from nToSum as list L, and then flattens it so that each list is a
       top level list.  Leading set n is the "prefix" list, and grows as you climb down the 
       sublists'''
    if type(L[0]) == int:  #base case:  you have exposed a pure integer
        return [n+L]       #take that integer, and prepend the leading set n
    else:
        Q = []
        for x in L:  # look at every sublist
            Q += compress(n+[x[0]],x[1])  # for each sublist, create top level lists recursively
        return Q                          # note:  append x[0] to leading set 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]]

Answer 1

Using a generator saves on memory (usexrange instead of range if using Python 2). This is what I came up with. It is very similar to your nToSum without the need for compress.

def sums(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(sums(5,100))
print('total permutations:',len(L))

# First and last 10 of list
for i in L[:10] + L[-10:]:
    print(i)

Output

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)