I tried to write code for this problem using Top down DP .
This is the code , I have written.
public static int CoinPermutation(int[] arr , int amount , int[] strg){
if(amount == 0){
return 1 ;
}
if(amount < 0){
return 0 ;
}
if(strg[amount] != -1){
return strg[amount] ;
}
int res = 0 ;
for(int i = 0 ; i < arr.length ; i++){
int smallProblem = CoinPermutation(arr,amount-arr[i],strg) ;
res += smallProblem ;
}
strg[amount] = res ;
return res ;
}
This code is working absolutely fine for all the test cases except 1 test case .
If the given input contains 0 as denomination , then this code is throwing an exception of StackOverFlow .
Can you tell me , what are the changes that has to be done to this code , so that it handles the cases where 0 is also a denomination .