package hackerrank;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * https://www.hackerrank.com/challenges/coin-change
 */
public class CoinChange {
    private static int coinChange(int n, int[] coins) {
        return coinChange(n, coins, new HashMap<>());
    }

    private static int coinChange(int n, int[] coins, Map<Integer, Integer> memo) {
        if (n < 0) {
            return 0;
        }
        if (n == 0) {
            return 1;
        }
        int numChange = 0;
        for (int coin : coins) {
            numChange += coinChange(n - coin, coins, memo);
        }
        return numChange;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] coins = new int[m];
        for (int i = 0; i < m; i++) {
            coins[i] = in.nextInt();
        }
        System.out.println(coinChange(n, coins));
    }
}

@@ -14,16 +14,41 @@
 rrank;%0A%0A
+import java.util.Arrays;%0A
 import j
@@ -212,35 +212,36 @@
  private static 
-int
+long
  coinChange(int 
@@ -232,34 +232,36 @@
  coinChange(
-int n, int
+long n, long
 %5B%5D coins) %7B%0A
@@ -311,16 +311,19 @@
 hMap%3C%3E()
+, 0
 );%0A    %7D
@@ -343,19 +343,20 @@
  static 
-int
+long
  coinCha
@@ -363,18 +363,20 @@
 nge(
-int n, int
+long n, long
 %5B%5D c
@@ -389,30 +389,72 @@
 Map%3C
-Integer, Integer%3E memo
+String, Long%3E memo,%0A                                   long prev
 ) %7B%0A
@@ -568,19 +568,138 @@
         
-int
+String key = n + %22%7C%22 + prev;%0A        if (memo.containsKey(key)) %7B%0A            return memo.get(key);%0A        %7D%0A        long
  numChan
@@ -719,19 +719,20 @@
    for (
-int
+long
  coin : 
@@ -732,32 +732,103 @@
 coin : coins) %7B%0A
+            if (prev %3E coin) %7B%0A                continue;%0A            %7D%0A
             numC
@@ -868,16 +868,22 @@
 ns, memo
+, coin
 );%0A     
@@ -879,32 +879,66 @@
 oin);%0A        %7D%0A
+        memo.put(key, numChange);%0A
         return n
@@ -1052,19 +1052,20 @@
         
-int
+long
  n = in.
@@ -1060,35 +1060,36 @@
 long n = in.next
-Int
+Long
 ();%0A        int 
@@ -1114,19 +1114,20 @@
         
-int
+long
 %5B%5D coins
@@ -1133,19 +1133,20 @@
 s = new 
-int
+long
 %5Bm%5D;%0A   
@@ -1219,32 +1219,60 @@
 nt();%0A        %7D%0A
+        Arrays.sort(coins);%0A
         System.o

Solve Coin Change