Project Euler 76: How many different ways can one hundred be written as a sum of at least two positive integers?

Project Euler 76: How many different ways can one hundred be written as a sum of at least two positive integers?

Written by on 24 December 2011

Topics: Project Euler

Problem 76 of Project Euler reads

It is possible to write five as a sum in exactly six different ways:

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

How many different ways can one hundred be written as a sum of at least two positive integers?

It is one of the shortest descriptions I have read for a long time and it will be one of the shortest solutions I have written for a short while. When I solved this I thought I was really clever to realise we could reuse an old solution for this. But apparantly the majority of the 9000+ other users who have solved it realised the same thing.

So which solution am I talking about? The solution to problem 31, the one about English currency denominations. We can reuse the dynamic programming solution for this problem. I think I have written the best explanation for that I can possibly come up with, so if you are not familiar with the solution for problem 31, I will suggest that you check it out before proceeding.

The difference here, is that instead of using the currency denominations we need to use every integer from 1 to 99 as possible values. This makes the solution look like

int target = 100;
int[] ways = new int[target + 1];
ways[0] = 1;

for (int i = 1; i <= 99; i++) {
    for (int j = i; j <= target; j++) {
        ways[j] += ways[j - i];

The result is the last field of the ways array. Executing this piece of code is

100 can be generated in 190569291 ways
Solution took 0,0092 ms

Wrapping up

I know this has been quite a short post, but since I just reused the solution from a previous exercise, I don’t really have much to add.

You can find the source code here, if you prefer it as a .cs file instead of snippets pasted onto a website.

Comments, alternative solutions and questions are as always very welcome.

The photo for todays blog post is kindly shared by Rodrigo Denúbila under the creative commons license. My derivative crop is of course shared under the same license.

13 Comments For This Post I'd Love to Hear Yours!

  1. JM says:

    Hii.. Sir Iam new to Dynamic Programming.. Please can you explain me how you choose the trival case her ways[0] = 1.

  2. Kristian says:

    It is merely a matter to get the calculations to fit, and not really something that makes a whole lot of physical sense. However, I think you should read the solution to problem 31, as that is more elaborated.

  3. JM says:

    Thanks for your reply sir.. the explanation to problem 31 helps me a lot..

  4. Ryan Gallagher says:

    How does this explain 100 you only do the number 4

  5. Kristian says:

    I don’t know how to answer this, but I think you are missing an integral of the post. The answer is that there are a little less than 200 mio ways to write 100 as a sum of 2 or more positive integers, so I don’t think it will be wise to write all of them.

  6. Afshin says:

    There is a more efficient way to solve this problem ( by using petagonal number theorem)
    take a look at

    p(n) = p(n-1) + p(n-2) – p(n-5) – p(n-7) + …

  7. Kristian says:

    Hi Afshin

    Thanks for noting that. I realized that when I solved problem 78 where I use a generating function based on the pentagonal numbers.

  8. Akkad says:

    DP solution to coin change problem solves it by using a 2D array. The function comes out to be something like:
    C(N,m) = C(N,m – 1) + C(N – Sm,m)

    I am finding it hard to figure out how this fit into a single array. Can you give me the recursive function? Or the logic behind this?

  9. cantonios says:

    It seems to me that the pentagonal number theorem and the DP coin change problem are exactly the same. According to the wiki article on partitions, the algorithm for computing p(n) uses memoization and the sets: p(n,m), the number of ways of partitioning n into m sets. This is equivalent to finding “the number of ways to sum $n using m coins”.

  10. Richard says:

    I solved problem 78 before 76. Having created the function to calculate p(n) for problem 78, I just used it again for 76. The only twist is that for problem 76 the answer is p(n)-1 because only solutions which are a sum of 2 or more digits are counted.

  11. Jean-Marie Hachey says:

    Table 1
    Variation of different ways numbers 1 to 20 can be written as the sum of at least two positive integers.
    [Re: Project Euler , Problem 76]


    Fig. 1
    Variation of different ways numbers 1 to 20 can be written as the sum of at least two positive integers. Polynomial regression.
    [Re: Project Euler , Problem 76]

    A good quality polynomial regression of order 3 is obtained as shown in Fig. 1.

    List of partitions is available on OEIS website (4)


    Sources :
    1) Microsoft Visual C# 2010 Express
    2) Project Euler – Problem 76 (Kristian’s algorithm)
    3) Microsoft Office Excel (2007)
    4) OEIS

  12. Jean-Marie Hachey says:

    As seen in Table 1, the three algos give the same output for 100 and 121.
    The difference begins at 122.

    Table 1
    Comparisons of results obtained with
    different algorithms for PE76
    [Re: Project, Problem 76]


    Sources :

    1) The On-Line Encyclopedia of Integer Sequences (OEIS),
    -1 + number of partitions of n.
    N. J. A. Sloane and Vincenzo Librandi,
    2) Project Euler – Problem 76 (Kristian’s algorithm)
    3) Project Euler – Problem 76 (Sir Alan’s algorithm)
    4) Project Euler – Problem 76 (Dreamshire’s algorithm)
    5) Microsoft Visual C# 2010 Express
    6) Microsoft Office Excel (2007)

  13. Geoff says:

    Hi, thanks for the post. I am looking to do something similar. I have 5 funds. Fund A, B, C, D, E. Each can have a positive integer value between 0 and 100. I would like to know the combinations using up to 5 funds to sum to 100. I would also like to know what each combination is. An example:

    A is 0, B is 20, C is 30, D is 50 and E is 100.

    Thanks in advance. 🙂

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.