​CoinChanging problem

​One another interesting interview problem is to find the minimum number of coins required to get some amount.
You will be having a list of available denominations of coins with unlimited numbers.
Like coins denominations is - {1, 2, 5, 10} with each of unlimited counts and we have to find the minimum number of coins required to get 13.
Here answer will be 3 with 1 coin of 10, 1 of 2 & 1 of 1.
We can have limit on available number of coins for each denomination later.
Below code will give you the result like - {3={1=1, 2=1, 10=1}}

import java.util.Arrays;
import java.util.HashMap;

public class CoinChanging {

 public static void main(String[] args) {
  int[] coins = {1, 2, 5, 10};
  int total = 13;
  System.out.println(count(coins, total));
 }

 public static HashMap<Integer, HashMap<Integer, Integer>> count(int[] coins, int total) {

  Arrays.sort(coins);
  int[] totals = new int[total+1];
  int[] track = new int[total+1];

  int i = 0;
  for(int coin : coins) {
   int k = 1;
   while(k <= total) {
    if(k - coin == 0) {
     totals[k] = 1;
     track[k] = i;
    } else if(k-coin >= 0 && totals[k] > totals[k-coin] + 1 || totals[k] == 0){
     totals[k] = totals[k-coin] + 1;
     track[k] = i;
    }
    k++;
   }
   i++;
  }
  int sum = total;
  HashMap<Integer, Integer> counts = new HashMap<>();
  while(sum > 0) {
   int temp = sum - coins[track[sum]];
   if(counts.get(coins[track[sum]]) == null) {
    counts.put(coins[track[sum]], 1);
   } else {
    int cur = counts.get(coins[track[sum]]);
    counts.put(coins[track[sum]], cur+1);
   }
   sum = temp;
  }
  
  HashMap<Integer, HashMap<Integer, Integer>> result = new HashMap<>();
  result.put(totals[total], counts);
  return result;
 }
}