In Java: static int pickCoins(int valueIn, int[] coinsIn) { if (valueIn == 0) return 0; int num = 0; Set first = new HashSet(), second = new HashSet(), temp; first.add(valueIn); while (!first.isEmpty()) { num++; for (int i : first) { for (int j : coinsIn) { if (i-j == 0) return num; else if (i-j > 0) second.add(i-j); } // for-coinsIn } //for-first // swap first and second temp = second; first.clear(); second = first; first = temp; } //while return -1; } //pickCoins()

public static int totalNum(int valueIn, int[] coinsIn){ Arrays.sort(coinsIn); int num = 0; for(int i = (coinsIn.length-1); i >= 0; i--){ num += valueIn/coinsIn[i]; valueIn = valueIn % coinsIn[i]; if (valueIn == 0) return num; } return -1; } From main: int[] coins = { 1, 7, 5, 11 }; int amount = 100;// $1 tatalNum(amount, coins)

Sorry. My description was a little ambiguous. I didn't mean using a quarter, dime, nickel, and penny. The coins themselves could have arbitrary values. For example, Coin A is worth 16 cents, Coin B is worth 9 cents, coin C is worth 4 cents, and coin D is worth 1 cent. Now using coins A, B, C, and D, find the fewest amount of coins to get to value X. Now the typical reaction is to subtract the largest coin from the total until the total is less then the value of that coin, repeat with the next smallest coin, and so on and count up the coins (like how the previous poster solved it). But that solution doesn't always work. Given the coin values described above, get the fewest coins for value X=18. This algorithm would result in 1 coin A and 2 coin Ds for a total of three coins but the correct answer is 2 coin Bs. The original solution with the tree and breadth first search is the way to get this answer.