For a given integer a, find all unique combinations of positive integers that sum up to a

Question

Not a homework question. I was going through the questions here and I came across this question. Someone has answered it. I have tried a lot to understand the recursion used but I am not able to get it. Could someone explain it to me?

Write a function, for a given number, print out all different ways to make this number, by using addition and any number equal to or smaller than this number and greater than zero.

For example, given a = 5, we have the following seven ways to make up 5:

• 1, 1, 1, 1, 1
• 1, 4
• 1, 1, 1, 2
• 1, 1, 3
• 2, 3
• 1, 2, 2
• 5

The solution from the site is in C++:

void printSeq( int num , int a[] , int len , int s )
{
    if( num <= 0 )
    {
        for( int j = 0 ; j < len ; j++ )
            cout << a[ j ] << "," ;
        cout << endl;

        return;
    }

    for(int i = s ; i <= num ; i++)
    {
        a[ len ] = i;
        printSeq( num - i , a , len + 1 , i );
    }
}

int main()
{
    int a[5];
    printSeq(5,a,0,1);
    cin.get();
    return 0;
} 

Answer 1

When facing a problem like this it is often a good idea to take a step back from your editor/IDE and think about the problem by drawing out a simple case on a whiteboard. Don't even do pseudo-code yet, just draw out a flowchart of how a simple case (e.g. a = 3) for this problem would turtle all the way down. Also, don't worry about duplicate combinations at first. Try to find a solution which gives you all the desired combinations, then improve your solution to not give you duplicates. In this case, why not look at the manageable case of a = 3? Let me draw a little picture for you. A green checkmark means that we have arrived at a valid combination, a red cross means that a combination is invalid.

As you can see, we start with three empty subcombinations and then build three new subcombinations by appending a number to each of them. We want to examine all possible paths, so we choose 1, 2 and 3 and end up with [1], [2] and [3]. If the sum of the numbers in a combination equals 3, we have found a valid combination, so we can stop to examine this path. If the sum of the numbers in a combination exceeds 3, the combination is invalid and we can stop as well. If neither is the case, we simply continue to build combinations until we arrive at either a valid or invalid solution.

Since your question seems to be primarily about how to work out a recursive solution for this kind of problems and less about specific syntax and you just happened to find a C++ solution I am going to provide a solution in Python (it almost looks like pseudo code and it's what it know).

def getcombs(a, combo = None):
    # initialize combo on first call of the function
    if combo == None:
        combo = []

    combosum = sum(combo) # sum of numbers in the combo, note that sum([]) == 0
    # simple case: we have a valid combination of numbers, i.e. combosum == a
    if combosum == a:
        yield combo # this simply gives us that combination, no recursion here!
    # recursive case: the combination of numbers does not sum to a (yet)
    else:
        for number in range(1, a + 1): # try each number from 1 to a               
            if combosum + number <= a:  # only proceed if we don't exceed a
                extcombo = combo + [number] # append the number to the combo
                # give me all valid combinations c that can be built from extcombo
                for c in getcombs(a, extcombo):
                    yield c

Let's test the code!

>>> combos = getcombs(3)
>>> for combo in combos: print(combo)
... 
[1, 1, 1]
[1, 2]
[2, 1]
[3]

This seems to work fine, another test for a = 5:

>>> combos = getcombs(5)
>>> for combo in combos: print(combo)
... 
[1, 1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 2, 1]
[1, 1, 3]
[1, 2, 1, 1]
[1, 2, 2]
[1, 3, 1]
[1, 4]
[2, 1, 1, 1]
[2, 1, 2]
[2, 2, 1]
[2, 3]
[3, 1, 1]
[3, 2]
[4, 1]
[5]

The solution includes all seven combinations we were looking for, but the code still produces duplicates. As you may have noticed, it is not necessary to take a number smaller than the previous chosen number to generate all combinations. So let's add some code that only starts to build an extcombo for numbers which are not smaller than the currently last number in a combination. If the combination is empty, we just set the previous number to 1.

def getcombs(a, combo = None):
    # initialize combo on first call of the function
    if combo == None:
        combo = []

    combosum = sum(combo) # sum of numbers in combo, note that sum([]) == 0
    # simple case: we have a valid combination of numbers, i.e. combosum == a
    if combosum == a:
        yield combo # this simply gives us that combination, no recursion here!
    # recursive case: the combination of numbers does not sum to a (yet)
    else:
        lastnumber = combo[-1] if combo else 1 # last number appended
        for number in range(lastnumber, a + 1): # try each number between lastnumber and a
            if combosum + number <= a:
                extcombo = combo + [number] # append the number to the combo
                # give me all valid combinations that can be built from extcombo
                for c in getcombs(a, extcombo):
                    yield c

Once again, let's test the code!

>>> combo = getcombs(5)
>>> for combo in combos: print(combo)
... 
[1, 1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 3]
[1, 2, 2]
[1, 4]
[2, 3]
[5]

The presented solution may not be the most efficient one that exists, but hopefully it will encourage you to think recursively. Break a problem down step by step, draw out a simple case for small inputs and solve one problem at a time.