Doubt Coin Change problem

#1

https://ide.codingblocks.com/s/123677 what will be recursive approach of this problem
what mistake i am doing in my code ??

question-Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, … , Sm} valued coins, In how many ways can we make the change? The order of coins doesn’t matter.

Input Format
First line of input contain two space separated integers N and M. Second line of input contains M space separated integers - value of coins.

Constraints
1<=N<=250 1<=m<=50 1 <= Si <= 50

Output Format
Output a single integer denoting the number of ways to make the given change using given coin denominations.

Sample Input
10 4
2 5 3 6
Sample Output
5

#2


hi mahavir
see your code will producing different permutation not combination.
here order not matter for ex one possible combination is 2 5 3
but your code along with this produce (2 3 5) , (3 2 5) , (3 5 2) etc.
i have make some modification in your code see it now it is giving correct ans

#3

@Saurabh2 i dint understand your recursive case line num 11 and 13
please explain line 11 and 13

#4

if(cent==0){
return 1;
} is cent ==0 you should return 0 because there is no way to to make change

#5

@Saurabh2 please resolve my doubt

#6

11 if (n <=0 && cent >= 1) return 0; this means if n<=0 means all coins has selected but not get get ans(cent is not 0) so return 0(no combination possible)

13 return totalchange(arr,cent,n-1)+totalchange(arr,cent-arr[n-1],n);
totalchange(arr,cent,n-1) this indicate that current coin is not chosen so
required cent value will no change but n will dec.
totalchange(arr,cent-arr[n-1],n) this indicate current coin is taken so required cent will dec by coin value.
and you have to return sum of both the answers(total no of ways).

1 Like
#7

when cent is 0 then it means we will get a combination of coins which will give us required value
ex: cent=10
and coins are 2 3 5
if we take 2 cent=8
if we take 3 cent=5
if we take 5 cent=0 now is cent is zero we will get a way

1 Like