Print All Combinations of Coins That Sum to an Amount - Java Solution

Introduction

Before doing this myself, I searched all over the place for a straightforward, readable solution to this problem online. After a short while (I have a low tolerance for these types of things), I just came up with my own algorithm.

The Problem

Given some array of coin values (e.g. quarters, dimes, and nickels), print out all possible combinations of these coins that sum to some variable x. It is assumed that you have an infinite amount of each type of coin available. So, for example, given an infinite supply of quarters and dimes, there are two ways to make 60 cents - 2 quarters and 1 dime, and 6 dimes.

This problem is similar to the knapsack problem, and it has been pretty thoroughly researched. It is NP-complete, so the runtime is exponential. Note that you can easily find the maximum number of ways that the total amount can be reached in O(m + n) time using dynamic programming, where m is the number of coins you are given, and n is the desired amount. This problem is more difficult, however. Below is my recursive solution, I highly recommend copy and pasting this code into your favorite text editor so that you can see the syntax highlighting and more easily distinguish the comments I made:

import java.util.*;

public class AllCoins {
    public static void main(String [] args) {
        int goal = 50;
        int [] coins = new int [] {25, 10, 5};

        // for formatting the string outputs
        Map<Integer, String> names = new HashMap<Integer, String>();
        names.put(25, "quarter(s)");
        names.put(10, "dime(s)");
        names.put(5, "nickel(s)");

        // to keep track of the current amounts of each type of coin
        Map<String, Integer> curr = new HashMap<String, Integer>();
        curr.put(names.get(25), 0);
        curr.put(names.get(10), 0);
        curr.put(names.get(5), 0);

        findCoins(goal, 0, coins, names, curr);
    }

    /*
        recursive function to print all combinations of coins that sum to goal
        @param left - amount left that we need to sum to with remaining coins
        @param index - index of current coin denomination we are working with
        @param coins - array of coin values
        @param names - map of names for string formatting
        @param curr - current amounts of each type of coin we have
    */
    private static void findCoins(int left, int index, int [] coins, Map<Integer, String> names, Map<String, Integer> curr) {
        // not the last type of coin
        if (index < coins.length - 1) {
            // if we have not reached our goal value yet
            if (left > 0) {
                int coinAmount = coins[index];
                if (coinAmount <= left) {
                    // try all possible numbers of current coin given the amount
                    // that is left
                    for (int i = 0; i <= left / coinAmount; i++) {
                        curr.put(names.get(coinAmount), i);
                        findCoins(left - coinAmount * i, index + 1, coins, names, curr);
                    }
                    // reset the current coin amount to zero before recursing
                    curr.put(names.get(coinAmount), 0);
                }
                // case when there is a coin whose value is greater than the goal
                else {
                    findCoins(left, index + 1, coins, names, curr);
                }
            }
            // we've reached our goal, print out the current coin amounts
            else {
                printCurr(curr);
            }
        }
        // last type of coin
        else {
            // if we have not reached our goal value yet
            if (left > 0) {
                int coinAmount = coins[index];
                if (coinAmount <= left) {
                    // if the remainder of our goal is evenly divisble by our last
                    // coin value, we can make the goal amount
                    if (left % coinAmount == 0) {
                        // add last coin amount and print current values out
                        curr.put(names.get(coinAmount), left / coinAmount);
                        printCurr(curr);

                        // reset this coin amount to zero before recursing
                        curr.put(names.get(coinAmount), 0);
                    }
                }
            }
            // we've reached our goal, print out the current coin amounts
            else {
                printCurr(curr);
            }
        }
    }

    private static void printCurr(Map<String, Integer> curr) {
        Iterator<String> iter = curr.keySet().iterator();
        while (iter.hasNext()) {
            String denom = iter.next();
            System.out.print(curr.get(denom) + " " + denom + " ");
        }
        System.out.println();
    }
}

When run, the output of the above program is the following:

10 nickel(s) 0 quarter(s) 0 dime(s)
8 nickel(s) 0 quarter(s) 1 dime(s)
6 nickel(s) 0 quarter(s) 2 dime(s)
4 nickel(s) 0 quarter(s) 3 dime(s)
2 nickel(s) 0 quarter(s) 4 dime(s)
0 nickel(s) 0 quarter(s) 5 dime(s)
5 nickel(s) 1 quarter(s) 0 dime(s)
3 nickel(s) 1 quarter(s) 1 dime(s)
1 nickel(s) 1 quarter(s) 2 dime(s)
0 nickel(s) 2 quarter(s) 0 dime(s)

Any questions? Feel free to ask in the comments below and I'll be quick to get back to you.