Problem Statement:
Task
Write a program that, given
The amount N to make change for and the number of types M of infinitely available coins
A list of M coins - C={C1,C2,C3,..,CM}C={C1,C2,C3,..,CM}
Prints out how many different ways you can make change from the coins to STDOUT.
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static long[][] diffCount = null;
public static void main(String args[] ) throws Exception {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int p = in.nextInt();
int[] input = new int[p];
for(int i=0;i<p;i++)
{
input[i] = in.nextInt();
}
Arrays.sort(input);
System.out.println(ways(n,input));
}
public static long ways(int n, int[] input) {
int[][] store = new int[n / input[0]][input.length];
diffCount = new long[input.length + 1][250 + 1];
long count = 0;
// intermediate sum calculation
for (int i = 0; i < input.length; i++) {
for (int j = 0; j < store.length; j++) {
if (j == 0) {
store[j][i] = store[j][i] + input[i];
} else {
if (store[j - 1][i] + input[i] <= n) {
store[j][i] = store[j - 1][i] + input[i];
} else
break;
}
}
}
count = getDiffPartCount(store, n, 0, 0);
return count;
}
public static long getDiffPartCount(int[][] store, int diff, int row, int index) {
long count = 0;
for (int i = index; i < store[0].length; i++) {
if (store[0][i] > diff)
continue;
for (int j = 0; j < store.length && store[j][i] <= diff
&& store[j][i] > 0; j++) {
if (diff == store[j][i]) {
count++;
break;
} else if (diff > store[j][i] && store[j][i] > 0) {
int act = diff - store[j][i];
long cnt = 0;
if (i + 1 < store[0].length && act > 0) {
if (diffCount[i + 1][act] == 0) {
cnt = getDiffPartCount(store, act, j, i + 1);
if (cnt == 0)
diffCount[i + 1][act] = -99;
else
diffCount[i + 1][act] = diffCount[i + 1][act]
+ cnt;
} else if (diffCount[i + 1][act] == -99) {
cnt = 0;
} else {
cnt = diffCount[i + 1][act];
}
if (cnt >= 1)
count = count + cnt;
continue;
} else {
continue;
}
} else {
break;
}
}
}
return count;
}
}