package leetcode;

/**
 * https://leetcode.com/problems/coin-change-2/
 */
public class Problem518 {
    public int change(int amount, int[] coins) {
        Result result = new Result();
        change(amount, coins, result);
        return result.result;
    }

    private static class Result {
        private int result;
    }

    private static void change(int amount, int[] coins, Result result) {
        if (amount <= 0) {
            if (amount == 0) {
                result.result++;
            }
            return;
        }
        for (int coin : coins) {
            change(amount - coin, coins, result);
        }
    }

    public static void main(String[] args) {
        Problem518 prob = new Problem518();
        System.out.println(prob.change(5, new int[]{1, 2, 5})); // 4
//        System.out.println(prob.change(3, new int[]{2})); // 0
//        System.out.println(prob.change(10, new int[]{10})); // 1
    }
}
@@ -12,16 +12,65 @@
 tcode;%0A%0A
+import java.util.HashMap;%0Aimport java.util.Map;%0A%0A
 /**%0A * h
@@ -204,208 +204,94 @@
     
-Result result = new Result();%0A        change(amount, coins, result);%0A        return result.result;%0A    %7D%0A%0A    private static class Result %7B%0A        private int result;%0A    %7D%0A%0A    private static void c
+return coinChange(amount, coins, new HashMap%3C%3E());%0A    %7D%0A%0A    private static int coinC
 hang
@@ -321,21 +321,34 @@
 ns, 
-Result result
+Map%3CInteger, Integer%3E memo
 ) %7B%0A
@@ -427,21 +427,50 @@
   re
-sult.result++
+turn 1;%0A            %7D%0A            return 0
 ;%0A  
@@ -467,37 +467,73 @@
 turn 0;%0A        
+%7D%0A
     
-%7D
+    if (memo.containsKey(amount)) %7B
 %0A            ret
@@ -535,16 +535,33 @@
   return
+ memo.get(amount)
 ;%0A      
@@ -556,32 +556,55 @@
 unt);%0A        %7D%0A
+        int count = 0;%0A
         for (int
@@ -633,16 +633,29 @@
        c
+ount += coinC
 hange(am
@@ -678,26 +678,79 @@
 ns, 
-result);%0A        %7D
+memo);%0A        %7D%0A        memo.put(amount, count);%0A        return count;
 %0A   

Update problem 518