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:
- $10 + 8$
- $6 + 4 + 8$
- $1 + 2 + 3 + 4 + 8$
- ....
Is there any algorithm or formula for this problem?
In terms of algorithms, one way you can approach it is by building up a table.
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.
Remember to use memoization so that you don't have to repeatedly do massive recursive calls.