well, what i did was this.

say you want to sum to 10 with 4 coins.

you can do it this way: (1,1,1,7), (1,1,2,6),(1,2,2,5),(2,2,2,4),(2,2,3,3).

every other way is just a permutation of the above. (from the

example given in the problem i assumed we don't count permutations).

so in this case there are 5 ways to do it.

my code above simulates this by noting that if we add 1 to all the

coins except the last in turn, while subtracting 1 from the last coin each time, we've subtracted numberofcoins-1 from the last coin, and have gone

though numberofcoins-1 permutations.

The example above illustrates this.

To actually implement it, we just keep track of the last 2 coins.

we subtract numberofcoins-1 from the last and add 1 to the

second last until the

difference between the 2nd last and last coin is small

(ie, < numberofcoins -1), then we figure out how many are

actually left.

i think this is correct, but I keep getting WA.

one reply above implied that the number of ways is too large for an int. The largest number my code generates is ~40000.

Maybe somebody who got there's accepted could post some

cases with the correct output?

The code runs in 0.5 seconds.

If my algorithm is wrong, somebody please tell me now.

any input would be appreciated. I feel like i've made a really

dumb mistake...