1. class Solution {
  2.     /** Recursion */
  3.     public int count(int coins[], int sum) {
  4.         int n = coins.length;
  5.  
  6.         return countCombinations(coins, sum, n);
  7.     }
  8.  
  9.     public int countCombinations(int[] coins, int sum, int n)
  10.     {
  11.         // base condition: when sum becomes 0 then we found valid combination
  12.         if(sum == 0)
  13.             return 1;
  14.  
  15.         // base condition: when we reach end of array, no valid combination found
  16.         if(n == 0)
  17.             return 0;
  18.  
  19.         if(coins[n-1] <= sum)
  20.         {
  21.             // include the current coin into combination, and this coin can be used later too
  22.             int pick = countCombinations(coins, sum - coins[n-1], n);
  23.             // do not include the current coin into combination
  24.             int notPick = countCombinations(coins, sum, n-1);
  25.             return pick + notPick;
  26.         }
  27.         // when current coin has value greater than the required sum, skip the coin
  28.         return countCombinations(coins, sum, n-1);
  29.     }
  30.  
  31.  
  32.     /** Memoization */
  33.     public int count(int coins[], int sum) {
  34.         int n = coins.length;
  35.  
  36.         int[][] t = new int[n+1][sum+1];
  37.  
  38.         // when array size keeps on increasing but sum is 0, so we can have empty list
  39.         for(int i=0; i<n+1; i++)
  40.         {
  41.             Arrays.fill(t[i], 1);
  42.         }
  43.  
  44.         // when array size is 0, but sum keeps on increasing so we cannot have combination
  45.         for(int j=0; j<n+1; j++)
  46.         {
  47.             Arrays.fill(t[j], 0);
  48.         }
  49.  
  50.         return countCombinations(coins, sum, n, t);
  51.     }
  52.  
  53.     public int countCombinations(int[] coins, int sum, int n, int[][] t)
  54.     {
  55.         // base condition: when sum becomes 0 then we found valid combination
  56.         if(sum == 0)
  57.             return 1;
  58.  
  59.         // base condition: when we reach end of array, no valid combination found
  60.         if(n == 0)
  61.             return 0;
  62.  
  63.         if(t[n][sum] != 0)
  64.             return t[n][sum];
  65.  
  66.         if(coins[n-1] <= sum)
  67.         {
  68.             // include the current coin into combination, and this coin can be used later too
  69.             int pick = countCombinations(coins, sum - coins[n-1], n, t);
  70.             // do not include the current coin into combination
  71.             int notPick = countCombinations(coins, sum, n-1, t);
  72.             t[n][sum] = pick + notPick;
  73.             return t[n][sum];
  74.         }
  75.         // when current coin has value greater than the required sum, skip the coin
  76.         t[n][sum] = countCombinations(coins, sum, n-1, t);
  77.         return t[n][sum];
  78.     }
  79.  
  80.     /** Top-down approach */
  81.     public int count(int coins[], int sum) {
  82.         int n = coins.length;
  83.  
  84.         int[][] t = new int[n+1][sum+1];
  85.  
  86.         for(int i=0; i<n+1; i++)
  87.         {
  88.             for(int j=0; j<sum+1; j++)
  89.             {
  90.                 // when array is empty
  91.                 if(i == 0)
  92.                     t[i][j] = 0;
  93.  
  94.                 // when sum is 0
  95.                 if(j == 0)
  96.                     t[i][j] = 1;
  97.             }
  98.         }
  99.  
  100.         for(int i=1; i<n+1; i++)
  101.         {
  102.             for(int j=1; j<sum+1; j++)
  103.             {
  104.                 if(coins[i-1] <= j)
  105.                 {
  106.                     // include the current coin into combination, and this coin can be used later too
  107.                     int pick = t[i][j - coins[i-1]];
  108.                     // do not include the current coin into combination
  109.                     int notPick = t[i-1][j];
  110.                     t[i][j] = pick + notPick;
  111.                 }
  112.                 else
  113.                     t[i][j] = t[i-1][j];
  114.             }
  115.         }
  116.         return t[n][sum];
  117.     }
  118. }