# How to find random numbers that can sum up to n?

I have a random integer $n$ and another integer called the summary. I want to know how many ways I can sum a subset of numbers from $1$ to $n$ to produce the value of summary.

For example, I have $1,2,3,4,5,6,7,8,9,10$ and the summary is $18$. The expect result is:

1. $10 + 8$
2. $6 + 4 + 8$
3. $1 + 2 + 3 + 4 + 8$
4. ....

Is there any algorithm or formula for this problem?

-
Do you want to know the number of different subsets of $\{1\ldots n\}$ that sum to $S$ (your summary), do you want to know how to list all of them, or do you want to know how to choose one of them at random? Your question seems to ask all three simultaneously. – Steven Stadnicki Feb 27 '13 at 4:05

Let $P(S, n)$ be the number you are interested in, then $$P(s,n) = P(s-n, n-1) + P(s-n+1, n-2) + ... + P(s-2, 1)$$
Then go around building up a table and keeping in mind $P(0, n) = 1$ and $P(x, n) = 0$ when $x < 0$. I haven't fully checked if this algorithm works so report back on your findings.