Coin change Geeks For Geeks

 class Solution

{

    public long count(int arr[], int m, int n) 

    { 

       long t[][]=new long[m+1][n+1];

       for(int i=0;i<m+1;i++){

           for(int j=0;j<n+1;j++){

               if(i==0){

                   t[i][j]=0;

               }

               if(j==0){

                   t[i][j]=1;

               }

           }

           

       }

       for(int i=1;i<m+1;i++){

           for(int j=1;j<n+1;j++){

               if(arr[i-1]>j){

                   t[i][j]=t[i-1][j];

               }

               else{

                   t[i][j]=(t[i-1][j] + t[i][j-arr[i-1]]);

               }

           }

           

       }

       return t[m][n];

       

    } 

}

Approach: Dynamic Programming

Application of Subset Sum problem with just one modification of traversing one element several times(as it is unbounded knapsack).

Time: O(Array Size* Sum)[GFG Time: 0.6/1.5]

Space:O(Sum)

Thanks For Reading.😇