okay, this is the problem (variation of the knapsack coins problem): you've got 4 coin types:

1 cent, 2 cents, 5 cents and a quarter...infinite amount of each. I'm supposed to find the number of ways in which the coins can be arranged to form the sum of some integer n...

well i... had an idea but it proved pretty wrong.

my idea was to check all the possible ways of forming n with two other numbers, and save the solution as number of needed for the first times number of needed for the second, the problem is it is not always the case, as you can get large numbers cause of repetitions, for example 6:

2 + 4

two ways to make 2 ( 2, 1+1 )

three ways to make 4( 2+2, 1+1+1+1, 2+1 )

multiplied... 6 ways? nope...5

1+1+1+1+1+1

2+1+1+1+1

2+2+1+1

2+2+2

5+1... damn...

## Recommended Answers

Jump to PostFortunately, no need to count ways yourself. Let a dumb computer do that ;)...

Jump to PostAs usually: by solutions space reduction. Start from the largest coin type then recursively arrange the rest of sum with smaller set of coins and so on. Count all good solutions (with multiply and add operators;))...

Jump to PostNope. You have troubles with integer arithmetics.

For two cent coin: possible 0 or 1.

1st case: 3 - 0 = 3, for 1 cent coins 1 solution (1+1+1); 1 solution subtotal

2nd case: 3 - 2 = 1, for 1 cent coin 1 solution (1); 1 solution subtotal

1 …

Jump to PostSorry, I have no time to inspect your implementation carefully, but no need in arrays in this algorithm (except coins which must be a parameter of a recursive function). No need in <algorithm> header or MOD macros too.

It must be a very fast (and short) code...

Jump to PostWell, it's a good time to change notes:

`/// Must be coin[0] < coin[1] < ... < coin[n-1] int NumberOfWays(int sum, const int coin[], int n) { if (0 >-- n) return 0; int high = coin[n]; if (n == 0) return sum % high? 0: 1; …`

## All 17 Replies

We're a friendly, industry-focused community of 1.21 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.