mkmeden's blog

By mkmeden, history, 21 month(s) ago, In English

In the standard coin exchange problem were each denominations are available infinite times and we need to find the number of ways in which we can form the target value :

for a recursive function int fun(int n , int val) and the arr contains the denominations.

this is how the possible cases for the recursive calls should be .

Spoiler

But before seeing the solution I thought it like this instead ( definitely wrong )

Spoiler

I considered one more case too, where we take the coin and move to the next index . I cant find a reasoning why this is wrong logically .

Might be a stupid doubt but cant get over it just like that. Can anyone tell me why is it wrong to consider that case.

Thanks

  • Vote: I like it
  • +1
  • Vote: I do not like it

| Write comment?
»
21 month(s) ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

fun(n — 1, val — arr[n]) will be counted as part of fun(n, val — arr[n]) follwed by fun(n — 1, val — arr[n]), so you are going to be double counting.