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

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.