Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
2  
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

1 Answer 1

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|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.