1. class Solution {
  2.     // idea: Do not add +1 when picking a coin. Each valid combination is counted exactly once.
  3.  
  4.     /** Recursion */
  5.     public int change(int amount, int[] coins) {
  6.         int n = coins.length;
  7.  
  8.         return findWays(coins, amount, n);
  9.     }
  10.  
  11.     public int findWays(int[] coins, int amount, int n)
  12.     {
  13.         // base condition: when amount becomes 0 then we found valid combination
  14.         if(amount == 0)
  15.             return 1;
  16.  
  17.         // base condition: No coins left
  18.         // At this point, if amount > 0 (positive), we cannot form the remaining amount, because there are no coins left to use.
  19.         // Returning 0 here would mean 0 coins are needed, which is incorrect, because we cannot form the positive amount with no coins.
  20.         if(n == 0)
  21.             return 0;
  22.  
  23.         if(coins[n-1] <= amount)
  24.         {
  25.             int pick = findWays(coins, amount-coins[n-1], n);
  26.             int notPick = findWays(coins, amount, n-1);
  27.             return pick + notPick;
  28.         }
  29.         return findWays(coins, amount, n-1);
  30.     }
  31.  
  32.     /** Memoization */
  33.     public int change(int amount, int[] coins) {
  34.         int n = coins.length;
  35.  
  36.         // create a matrix
  37.         int[][] t = new int[n+1][amount+1];
  38.  
  39.         // initialise the matrix
  40.         for(int i=0; i<n+1; i++)
  41.             Arrays.fill(t[i], 1);
  42.  
  43.         for(int j=0; j<n+1; j++)
  44.             Arrays.fill(t[j], 0);
  45.  
  46.         return findWays(coins, amount, n, t);
  47.     }
  48.  
  49.     public int findWays(int[] coins, int amount, int n, int[][] t)
  50.     {
  51.         // base condition: when amount becomes 0 then we found valid combination
  52.         if(amount == 0)
  53.             return 1;
  54.  
  55.         // base condition: No coins left
  56.         // At this point, if amount > 0 (positive), we cannot form the remaining amount, because there are no coins left to use.
  57.         // Returning 0 here would mean 0 coins are needed, which is incorrect, because we cannot form the positive amount with no coins.
  58.         if(n == 0)
  59.             return 0;
  60.  
  61.         if(t[n][amount] != 0)
  62.             return t[n][amount];
  63.  
  64.         if(coins[n-1] <= amount)
  65.         {
  66.             int pick = findWays(coins, amount-coins[n-1], n, t);
  67.             int notPick = findWays(coins, amount, n-1, t);
  68.             t[n][amount] = pick + notPick;
  69.             return t[n][amount];
  70.         }
  71.         t[n][amount] = findWays(coins, amount, n-1, t);
  72.         return t[n][amount];
  73.     }
  74.  
  75.  
  76.     /** Top-down */
  77.     public int change(int amount, int[] coins) {
  78.         int n = coins.length;
  79.  
  80.         // create a matrix
  81.         int[][] t = new int[n+1][amount+1];
  82.  
  83.         // initialise the matrix with base condition
  84.         for(int i=0; i<n+1; i++)
  85.         {
  86.             for(int j=0; j<amount+1; j++)
  87.             {
  88.                 // when we reach end of the array
  89.                 if(i == 0)
  90.                     t[i][j] = 0;
  91.  
  92.                 // when sum is always 0, then empty subset
  93.                 if(j == 0)
  94.                     t[i][j] = 1;
  95.             }
  96.         }
  97.  
  98.         for(int i=1; i<n+1; i++)
  99.         {
  100.             for(int j=1; j<amount+1; j++)
  101.             {
  102.                 if(coins[i-1] <= j)
  103.                 {
  104.                     int pick = t[i][j - coins[i-1]];
  105.                     int notPick = t[i-1][j];
  106.                     t[i][j] = pick + notPick;
  107.                 }
  108.                 else
  109.                     t[i][j] = t[i-1][j];
  110.             }
  111.         }
  112.         return t[n][amount];
  113.     }
  114. }