Algorithm to determine coin combinations

Question

I was recently faced with a prompt for a programming algorithm that I had no idea what to do for. I've never really written an algorithm before, so I'm kind of a newb at this.

The problem said to write a program to determine all of the possible coin combinations for a cashier to give back as change based on coin values and number of coins. For example, there could be a currency with 4 coins: a 2 cent, 6 cent, 10 cent and 15 cent coins. How many combinations of this that equal 50 cents are there?

The language I'm using is C++, although that doesn't really matter too much.

edit: This is a more specific programming question, but how would I analyze a string in C++ to get the coin values? They were given in a text document like

4 2 6 10 15 50 

(where the numbers in this case correspond to the example I gave)

Answer 1

This problem is well known as coin change problem. Please check this and this for details. Also if you Google "coin change" or "dynamic programming coin change" then you will get many other useful resources.

Answer 2

Here's a recursive solution in Java:

// Usage: int[] denoms = new int[] { 1, 2, 5, 10, 20, 50, 100, 200 };       
// System.out.println(ways(denoms, denoms.length, 200));
public static int ways(int denoms[], int index, int capacity) {
    if (capacity == 0) return 1;
    if (capacity < 0 || index <= 0 ) return 0;
    int withoutItem = ways(denoms, index - 1, capacity); 
    int withItem = ways(denoms, index, capacity - denoms[index - 1]); 
    return withoutItem + withItem;
}