Dynamic Programming Coin Change Problem - Print Coins Used Java

Question

So I have the coin change problem figured out and I understand how it works and everything but I cant seem to figure out how to print out how many of each coin is used. For example with the amount of 12 and the coin array of 1, 5, and 10 I want the output to look like:

Penny.    Nickel.    Dime
12.       0.         0
7.        1.         0
2.        2.         0
2.        0.         1

How would I go about printing that out? The code I currently have is:

public class codingChallenge {
public static void main(String[] args) {
    int [] coinsArray = {1, 5, 10};
    System.out.println(change(12, coinsArray));
}

public static int change(int amount, int[] coins){
    int[] combinations = new int[amount + 1];

    combinations[0] = 1;

    for(int coin : coins){
        for(int i = 1; i < combinations.length; i++){
            if(i >= coin){
                combinations[i] += combinations[i - coin];
                System.out.println(coin);
            }
        }
        System.out.println();
    }

    return combinations[amount];
}

}

Any help is VERY appreciated. Thanks!

Duplicate: https://stackoverflow.com/questions/1106929/how-to-find-all-combinations-of-coins-when-given-some-dollar-value — Rahul Jain, Dec 21 '20 at 17:28
@Rahul Jain I don’t think that’s really a duplicate because that is talking about the actual concept. I am looking for how to print it out like that. I have the concept and the code complete for finding how many possible outcomes, I just need to figure out how to show what the possible outcomes are. — Collin Stewart, Dec 21 '20 at 18:13
Your `change` method appears to only return the number of permutations (in this case 4), not the actual sets of values needed to print the results as you want them. Can you include the code (or at least the resulting data structure) that contains the sets of coins? — Rangi Keen, Dec 22 '20 at 00:14

score 0 · Accepted Answer · answered Dec 22 '20 at 01:21

Assuming you have a collection of coin permutations similar to the following

Collection<List<Integer>> permutations = List.of(
        List.of(12, 0, 0),
        List.of(7, 1, 0),
        List.of(2, 2, 0),
        List.of(2, 0, 1)
);

Then you can convert that to a table by calling printPermutations:

private static final String HEADER = "Penny     Nickel     Dime";
private static final String COIN_FORMAT = "%-10d";

private static void printPermutations(Collection<List<Integer>> permutations) {
    System.out.println(HEADER);
    String output = permutations.stream()
            .map(CoinChange::format)
            .collect(Collectors.joining("\n"));

    System.out.println(output);
}

private static String format(List<Integer> permutation) {
    return permutation.stream()
            .map(i -> String.format(COIN_FORMAT, i))
            .collect(Collectors.joining());
}

This obviously assumes the permutations include values for the same coins in your header. You could introduce a Coin class or enum and use a Map<Coin, Integer> instead of List<Integer> to make the solution a little more flexible, but the concept will remain the same.

Dynamic Programming Coin Change Problem - Print Coins Used Java

1 Answers1