title: Modifying the Coin Change problem to keep track of what coin is used (not minimum number)
body: <p>I wrote a simple coin change algorithm that currently ﬁnds the minimum number of coins needed to match the amount required to buy something. I'm trying to modify it so that it keeps track of the minimum number of coins of each denomination to be used and I'm falling a bit short. So, if you were to pass the number 6 to the function, it would say that the minimum number of coins needed is 2 (I already have that down) and that the combination of coins to do so is a 4 cent coin and a 2 cent coin. Here's my code:</p>
  
  <pre><code>coins[5] = {1, 2, 4, 17, 28} //effectively kills any use of greedy algortihms
  count[m];
  int coins_needed_for(int m) {
  
  
  //Initilization- fills array w/ -1s
  for (int z = 1; z &lt; m+1; z++) {
      count[z] = -1;      
  }//for  
  
  //fills in appropriate values
  for (int j = 0; j &lt; 5; j++) {   
      if (coins[j] &lt; m)
          count[coins[j]] = 1;    
      else if (coins[j] == 1)
          return 1;   
      else
          break;
  }//for  
  
  
  //Execution 
  for (int p = 1; p &lt; m+1; p++) {     
      if (count[p] == -1) {           
          int min = 10000 //poor subsitute for infinity;
  
          for (int i = 0; i &lt; 5; i++) {               
  
              if (coins[i] &lt;= p) {                            
                  if (count[p-coins[i]] + 1 &lt; min) {
                      min = count[p-coins[i]] + 1;                            
                  }                   
              }//if           
          count[p] = min;         
          }//for          
      }//if               
  }//for  
  return count[m];
  }
  </code></pre>
  
  <p>I understand what is required, I'm just not sure what the best way is to go about doing it. Should I create another array, and if so, would it have to be two dimensional? Could I create a struct that keeps count of each coin is used for each possible m? I'm open to any suggestions. I'm not necessarily looking for a definite answer, just pointers and helpful advice. Asking for an answer for an assigned problem is just wrong. Thanks!</p>