Recursive backtracking algorithm for the 'coin change problem'

Viewed 73

I'm trying to solve the "Coin Change Problem" by implementing a recursive backtracking algorithm which will analyze all possible outcomes and show the optimal combination of coins. Unfortunately, I have no idea how I can compare the different branches of the tree diagram that is being created. Any idea?

public class CoinChange_Backtracking {
        
    static int[] coins = {3, 2, 1};
    static int amount = 3;
    static int index_coins = 0;
    static LinkedList ll = new LinkedList();
    
    
    public static void main(String[] args) {
        //Start Recursion and display result.
        ll = recursiveFunction(coins, amount, index_coins, ll);
        ll.print();
    }

    
    public static LinkedList recursiveFunction(int[] coins, int amount, int index_coins, LinkedList ll) {
        //The current coin is being omitted. (If index_coins + 1 is still within range.)
        if ((index_coins + 1) < coins.length) {
            recursiveFunction(coins, amount, index_coins + 1, ll);
        }
        
        //The current coin is not being omitted. (If there is still some change left and value of change isn't lower than value of current coin.)
        if (amount != 0) {
            if (amount >= coins[index_coins]) {
                ll.add(coins[index_coins]);
                ll = recursiveFunction(coins, amount - coins[index_coins], index_coins, ll);
            }
        }
        return ll;
    }
}
0 Answers
Related