I am trying to solve a DSA problem for Minimum coin change,For that trying to print all the combinations of coins needed to make a certain amount. Below are two programs one uses String as a param and other one uses ArrayList. String one seems to pring the correct output but ArrayList doesn't.
Input to question -
wt[] = {1,2,3}
cap : 5
n : wt.length
coin = ""
Below are the code samples -
For String as param :
private static int findMaxProfit(int[] wt, int cap, int n, String coin) {
if (cap == 0) {
System.out.println(coin);
return 1;
}
if (n == 0 || cap < 0) {
return 0;
}
if (wt[n - 1] <= cap) {
//Don't reduce n, when we are including the item in knapsack.
return findMaxProfit(wt, cap - wt[n - 1], n, coin + wt[n - 1] + ",") + findMaxProfit(wt, cap, n - 1, coin);
} else {
return findMaxProfit(wt, cap, n - 1, coin);
}
}
For Arraylist as param :
private static int findMinCoins(int[] wt, int cap, int n, List<Integer> list, boolean val) {
if (cap == 0) {
System.out.println(list);
return 1;
}
if (n == 0 || cap < 0) {
return 0;
}
if (wt[n - 1] <= cap) {
//Don't reduce n, when we are including the item in knapsack.
return findMinCoins(wt, cap - wt[n - 1], n, list, list.add(wt[n - 1])) + findMinCoins(wt, cap, n - 1, list, true);
} else {
return findMinCoins(wt, cap, n - 1, list, true);
}
}
Above code samples can be executed by passing the input for reference, Adding output of both the code samples below -
String output : 3,2, ArrayList output : [3, 2]
3,1,1, [3, 2, 1, 1]
2,2,1, [3, 2, 1, 1, 2, 2, 1]
2,1,1,1, [3, 2, 1, 1, 2, 2, 1, 1, 1, 1]
1,1,1,1,1, [3, 2, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1]