Min Coin Change problem using DP and backtracking

Suppose we have set of coins S={c1,c2,c3,...cn} and M
we need to find smallest number of coins to change M.
or find all <kj,cj> such that Sum ( kj*cj ) = M

Solution:
I used dynamic programming to solve the problem and also used backtracking to return all <kj,cj>:

for more information have a look at :
http://www.algorithmist.com/index.php/Min-Coin_Change

----------------------------------------------

map<int,int> min_coins(vector<int> pCoins,int pSum,int *pMinRequired)
{
 map<int,int> trace;//(pCoins.size());
 vector<int> mins(pSum+1);
 vector<int> prev(pSum+1);
 fill(mins.begin(),mins.end(),INFINITY);
 for(int i=0;i<pCoins.size();i++)
  trace.insert(make_pair<int,int>(pCoins[i],0));
 mins[0]=0;
 sort(pCoins.begin(),pCoins.end());
 for(int i=1;i<=pSum;i++)
 {
  int bestCoin=-1;
  for(int v=0;v<pCoins.size() && pCoins[v]<=i  ;v++)
   if(mins[i-pCoins[v]]+1<mins[i])
   {
    mins[i]=mins[i-pCoins[v]]+1;
    bestCoin=v;
    prev[i]=i-pCoins[v];
   }
   if(bestCoin !=-1)
    trace[i]=pCoins[bestCoin];
 }
 *pMinRequired= mins[pSum];
 int curr=pSum;
 map<int,int> ret;
 while(curr>0)
 {
  ret[trace[curr]]++;
  curr=prev[curr];
 }
 return  ret;
}

 void test_coins()
{
 vector<int> coins;
 coins.push_back(1);
 coins.push_back(5);
 coins.push_back(10);
 coins.push_back(25);
 int minreq,sum=30;
 map<int,int> result=min_coins(coins,sum,&minreq);
 cout << " min required for "<<sum<<"$ is to pick "<<minreq<<" coins as :"<<endl;
 for(map<int,int>::iterator it=result.begin();it!=result.end();it++)
  cout <<" pick "<<it->second <<" coins of "<<it->first<<endl;

}

---------------------------------------------