Find the no. of ways of getting a sum n with all positive integers less than n

Question

For a given number n, say 2 how many ways can we get a sum 2 using numbers less that 2.

1+1 = 2  
so, for 2 - just 1 way.

n = 3   
1+1+1=3  
1+2=3  
so,for 3 - it is 2 ways  
n = 4   
1+1+1+1=4  
1+1+2=4  
1+3=4  
2+2=4  

so, for 4 - it is 4 ways  

Can there be a generic pattern/solution to this question?

Answer 1

This problem is known as Partition Problem, see detail in the referenced link from wiki:

One way of getting a handle on the partition function involves an intermediate function p(k, n), which represents the number of partitions of n using only natural numbers at least as large as k. For any given value of k, partitions counted by p(k, n) fit into exactly one of the following categories:

smallest addend is k
smallest addend is strictly greater than k.

The number of partitions meeting the first condition is p(k, n − k). To see this, imagine a list of all the partitions of the number n − k into numbers of size at least k, then imagine appending "+ k" to each partition in the list. Now what is it a list of? As a side note, one can use this to define a sort of recursion relation for the partition function in term of the intermediate function, namely

1+ sum{k=1 to floor (1/2)n} p(k,n-k) = p(n),

The number of partitions meeting the second condition is p(k + 1, n) since a partition into parts of at least k that contains no parts of exactly k must have all parts at least k + 1.

Since the two conditions are mutually exclusive, the number of partitions meeting either condition is p(k + 1, n) + p(k, n − k). The recursively defined function is thus:

p(k, n) = 0 if k > n

p(k, n) = 1 if k = n

p(k, n) = p(k+1, n) + p(k, n − k) otherwise.

In fact you can calculate all values by memoization, to prevent from extra recursive calls.

Edit: As unutbu mentioned in his comment, at the end of calculation you should subtract 1 to output the result. I.e. all of the P values up to the last step should be calculated as wiki suggests, however at the very in the very end before outputting the result, You should subtract it by 1.