

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

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?

share|cite|improve this question
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

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.

share|cite|improve this answer

Your Answer


