Get All Numbers That Add Up To A Number

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 O

Solution 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]

Solution 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]

Solution 3:

Your question can be rephrased like this :

Given a number N, find all sets [S1, S2, S3 .....] where the sum of each set equals N. The size of the sets are given by the number L.

---

First let's consider the case of L=2.This means that you can have the following sets

(9,1) , (8,2), (7,3) , (6,4) , (5,5)

I'll call this the base solution and you'll soon see why.

Let's change our L to 3 now and redo our answer :

So let's consider the number 9. Does there exist such a list L such that sum(L) + 9 = 10 ? The obvious answer is No, but what's interesting here is not the answer but the question itself. We are basically asking for a set of 2 elements that can be summed up to be the number 1. This is the same problem that was solved by the base solution.

So therefore for each number x in [9,8,7,6,5,4,3,2,1] you try to find a set [a,b]such that x+a+b = 10.

This isn't a complete answer, but the idea is that you see the pattern here, and use recursion to calculate the base case as done above and then figure out the recursive call that will complete your solution. Good luck!