title: Compute the different ways to make (money) change from $167.37?
body: <p>This was an interview question:</p>
  
  <blockquote>
    <p>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?</p>
  </blockquote>
  
  <p>Anyone who could think of a space and time efficient algorithm and supporting code, please share.</p>
  
  <p><strong>Here is the code that i wrote (working) . I am trying to find the running time of this, any help is appreciated</strong></p>
  
  <pre><code>    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&lt;Float&gt; denominations,HashMap&lt;Float,Integer&gt; useddenominations)
      {
          if(amount&lt;0)
              return;
          if(amount==0)
          {
              Iterator&lt;Float&gt; 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 &lt; 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&lt;Float&gt; denominations = new LinkedList&lt;Float&gt;();
  
  
          denominations.add(ddollar);
          denominations.add(dollar);
          denominations.add(nikle);
  
          HashMap&lt;Float,Integer&gt; useddenominations = new HashMap&lt;Float,Integer&gt;();
          generatechange(amount, denominations, useddenominations);
      }
  
  }
  </code></pre>