Printing which coins are used to make a given amount

Question

I am trying to use recursion to find the minimum amount of coins to make a given amount. I have code that is able to list the minimum amount of coins required, but I can't seem to find a way to print off which coins were used to come up with the solution. I've searched and found similar examples, but I can't seem to properly apply it to this.

Here is what I have thus far:

import java.util.*;

public class Coins{

    public static int findMinCoins(int[] currency, int amount) {
        int i, j, min, tempSolution;

        min = amount;

        for (i = 0; i < currency.length; i++) {
            if (currency[i] == amount) {
                return 1;
            }
        }

        for (j = 1; j <= (amount / 2); j++) {
            tempSolution = findMinCoins(currency, j) + findMinCoins(currency, amount - j);
            if (tempSolution < min) {
                min = tempSolution;
            }
        }
        return min;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] USA =
        {1, 5, 10, 25, 50};
        System.out.println("Please enter an integer amount.");
        int amount = in.nextInt();
        int minCoins = findMinCoins(USA, amount);
        System.out.println("The minimum number of coins to make " + amount + " in United States currency is " + minCoins + ".");
        System.out.println("The coins used were:");
        /*Print coins used to find minCoins.*/
        in.close();
    }
}

An example of the code running thus far:

Please enter an integer amount.
17
The minimum number of coins to make 17 in United States currency is 4.
The coins used were:

If someone could give me some insight on how to do this, it would be much appreciated.

Answer 1

I think this should totally work with what you want to achieve. Just call the public static int findMinCoins(arg1, arg2) and it will output you the minimum number of coins and all the particular coins(It will show times the number of its occurrence) used using recursive algorithms.

public static int findMinCoins(int[] currency, int amount) {
    int min = findMinCoins(currency, amount, 0);
    System.out.print("The coins used were: ");
    return min;
}
private static int findMinCoins(int[] currency, int amount, int min){
    int number, value1, value2;
    int min1 = min;
    for(int i=currency.length-1; i>=0; i--) {
        if (amount>=currency[i]){
            amount = amount - currency[i];
            System.out.print(currency[i] + " ");
            min1 = findMinCoins(currency, amount, min1);
            return ++min1;
        }
    }
    return min1;
}