Behaviour of Arraylist passed as parameter in Recursion

60 Views Asked by At

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]                
0

There are 0 best solutions below