How to to determine the number of ways a number can be broken down into sums of smaller numbers

Question

My friend gave me this problem he was asked in an interview that he was not able to answer. After hours of thinking we were not able to come up with the solution.

Consider A number three. I need to write a program to count the different ways in which you can write the number as a sum of numbers less than the number.

For example:

If the number is 2, it can be written as sum(1,1)

if the number is 3, it can be written as sum(1,1,1), sum(1,2), sum(2,1)

if the number is 4, it can be written as sum(1,1,1,1), sum(1,3), sum(3,1), sum(1,2,1), sum(2,1,1), sum(1,1,2), sum(2,2). 7 different ways

If the number is 5, it can be written as sum(1,1,1,1,1), sum(1,1,1,2), sum(1,1,2,1), sum(1,2,1,1), sum(2,1,1,1) etc.

How can I write program to determine the number of ways a number can be broken down into sums of smaller numbers

I was able to come up with a solution for the problem if sum(1,2) and sum(2,1) are considered equivalent using the algorithm in http://www.programminglogic.com/integer-partition-algorithm/

But the problem is sum(1,2) and sum(2,1) are different. I can not see a pattern to do this at all.

Any help would be appreciated. I just want to know the solution.

Answer 1

Think of the number as a line of dots:

4     -> . . . .

Between two adjacent dots we can put a wall to break the number into smaller ones:

1+3   -> .|. . .
2+2   -> . .|. .
1+2+1 -> .|. .|.

For every of the n-1 gaps, we have the option of putting a wall or not, for a total of 2^(n-1) possibilities. However, putting no walls leaves us with just the number, which isn't allowed, so we remove that as a possibility for a final total of 2^(n-1)-1 solutions.