Compute the different ways to make (money) change from $167.37?

Question

This was an interview question:

Given an amount, say $167.37 find all the possible ways of generating the change for this amount using the denominations available in the currency?

Anyone who could think of a space and time efficient algorithm and supporting code, please share.

Here is the code that i wrote (working) . I am trying to find the running time of this, any help is appreciated

    import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;


public class change_generation {

    /**
     * @param args
     */

    public static void generatechange(float amount,LinkedList<Float> denominations,HashMap<Float,Integer> useddenominations)
    {
        if(amount<0)
            return;
        if(amount==0)
        {
            Iterator<Float> it = useddenominations.keySet().iterator();
            while(it.hasNext())
            {
                Float val = it.next();
                System.out.println(val +" :: "+useddenominations.get(val));
            }

            System.out.println("**************************************");
            return;
        }

        for(Float denom : denominations)
        {

            if(amount-denom < 0)
                continue;

            if(useddenominations.get(denom)== null)
                useddenominations.put(denom, 0);

            useddenominations.put(denom, useddenominations.get(denom)+1);
            generatechange(amount-denom, denominations, useddenominations);
            useddenominations.put(denom, useddenominations.get(denom)-1);
        }

    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        float amount = 2.0f;
        float nikle=0.5f;
        float dollar=1.0f;
        float ddollar=2.0f;

        LinkedList<Float> denominations = new LinkedList<Float>();


        denominations.add(ddollar);
        denominations.add(dollar);
        denominations.add(nikle);

        HashMap<Float,Integer> useddenominations = new HashMap<Float,Integer>();
        generatechange(amount, denominations, useddenominations);
    }

}

Answer 1

EDIT

This is a specific example of the combination / subset problem, answered here.

Finding all possible combinations of numbers to reach a given sum

--- I am retaining my answer below (as it was usefull to someone), however, admittedly, it is not a direct answer to this question ---

ORIGINAL ANSWER

The most common solution is dynamic programming :

First, you find the simplest way to make change of 1, then you use that solution to make change for 2, 3, 4, 5, 6, etc.... At each iteration, you "check" if you can go "backwards" and decrease the amount of coins in your answer. For example, up to "4" you must add pennies. But, once you get to "5", you can remove all pennies, and your solution has only one coin required : the nickel. But then, until 9, you again must add pennies, etc etc etc.

However, the dynamic programming methodology is not gauranteed to be fast.

Alternatively, you can use a greedy method, where you continually pick the largest coin possible. This is extremely fast , but doesnt always give you an optimal solution. However, if your coins are 1 5 10 and 25 , Greedy works perfectly, and is much faster then the linear programming method.

Answer 2

Memoization (kind of) is your friend here. A simple implementation in C:

unsigned int findRes(int n)
{
   //Setup array, etc.

   //Only one way to make zero... no coins.
   results[0] = 1;

   for(i=0; i<number_of_coins; i++)
   {
       for(j=coins[i]; j<=n; j++)
       {
           results[j] += results[j - coins[i]];
       }
   }

   return results[n];
}

So, what we're really doing here is saying:

1) Our only possible way to make 0 coins is 0 (this is our base case)

2) If we are trying to calculate value m, then let's check each coin k. As long as k <= m, we can use that coin k in a solution

3) Well, if we can use k in a solution, then couldn't we just take the solution for (m-k) and add it to our current total?