public class Solution {

public int change(int amount, int[] coins) {

return change(amount, coins, 0, new HashMap<String, Integer>());

}

public int change(int amount, int[] coins, int index, HashMap<String, Integer> memo){

if(amount == 0) return 1;

if(index >= coins.length) return 0;

String key = amount+"-"+ index;

if(memo.containsKey(key)) return memo.get(key);

int ways = 0;

int amountWithCoin = 0;

while(amountWithCoin <= amount){

int remaining = amount - amountWithCoin;

ways += change(remaining,coins,index+1, memo);

amountWithCoin += coins[index];

}

memo.put(key,ways);

return ways;

}

}