Get all numbers that add up to a number

Question

I'm trying to find a way to display all the possible sets of X integers that add up to a given integer. for example to get all 2 integer sets that make 5 I would have:

1, 4 2, 3 

Or for 3 integers that make 6:

1, 1, 4 1, 2, 3 2, 2, 2 

I only need whole numbers not including 0 and it only needs to work on up to about 15 in a set and 30 max. number.

I'm not even sure if this has a term mathematically. It's similar to factorisation I guess?

Answer 1

Here is one way to solve this problem:

def sum_to_n(n, size, limit=None):     """Produce all lists of `size` positive integers in decreasing order     that add up to `n`."""     if size == 1:         yield [n]         return     if limit is None:         limit = n     start = (n + size - 1) // size     stop = min(limit, n - size + 1) + 1     for i in range(start, stop):         for tail in sum_to_n(n - i, size - 1, i):             yield [i] + tail 

You can use it like this.

for partition in sum_to_n(6, 3):     print partition  [2, 2, 2] [3, 2, 1] [4, 1, 1] 

Answer 2

There's a snippet here:

from itertools import combinations, chain  def sum_to_n(n):     'Generate the series of +ve integer lists which sum to a +ve integer, n.'     from operator import sub     b, mid, e = [0], list(range(1, n)), [n]     splits = (d for i in range(n) for d in combinations(mid, i))      return (list(map(sub, chain(s, e), chain(b, s))) for s in splits) 

Use it like this:

for p in sum_to_n(4):         print p 

Outputs:

 [4] [1, 3] [2, 2] [3, 1] [1, 1, 2] [1, 2, 1] [2, 1, 1] [1, 1, 1, 1]