нужна помощь в исправлении этого кода при динамическом программировании/рекурсии при вычислении минимальных монет с использованием Java

У меня есть мой код, который предназначен для возврата минимальной конфигурации монет для внесения сдачи на заданную сумму. Он принимает два параметра, сумму и список номиналов. У меня нет ошибки компиляции, и программа работает, чтобы выдавать результат, но не совсем то, что я получаю. Любая помощь в этом очень ценится.

//this program calculates the minimum coins and distribution of
//denominations required to make change for a given sum
import java.util.*;
import java.io.*;
public class MinCoinCollectionBacktrack {
   private int sum;
   private List<Integer> coins;

   //constructor that takes sum and list of denominations
   //such as [1,5,10,25]
   public MinCoinCollectionBacktrack(int amount,List<Integer> denominationList) {
      sum=amount;
      coins=denominationList;
  }

  //calculate the minimum coins
  //uses map to store sum-->list of combinations
  //eg 3-->[2,1], 4 -->[2,2] for a given denomination list of [1,2,5]
  public  List<Integer> Mincoins() {
   Map<Integer, List<Integer>> lenChoices=new HashMap<Integer,List<Integer>>();
      int maxdenomination=Collections.max(coins);
      Integer sum1= new Integer(sum);
   return minCoins(lenChoices,sum,maxdenomination);

  }

  //wrapper method for MinCoins, it takes a map and updates as when
  //minimum configuration of a sum is found. stores the value
  //as described above
  private List<Integer> minCoins(Map<Integer, List<Integer>> lenChoices, int value,int maxdenomination) {
  //check if sum is a key in map, then return its value
   if (lenChoices.containsKey(value)) {
      return lenChoices.get(value);
  //check if the coinlist contains sum, if yes, it creates a
  //new key value pair to the Map
   } else if (coins.contains(value)) {
      List<Integer> newlist = new ArrayList<Integer>();
      newlist.add(value);
      lenChoices.put(value,newlist);
      return lenChoices.get(value); 
  //if the denomiation is > sum, just return empty list        
   } else if (maxdenomination > value) {
      List<Integer> newlist = new ArrayList<Integer>();
      lenChoices.put(value,newlist);
      return lenChoices.get(value);
  //here is where recursive backtracking happens    
   } else {
      int minLength=0;
      List<Integer> minConfig=new ArrayList<Integer>();
      for (int coin : coins) {
         List<Integer> results = minCoins(lenChoices,value - coin,maxdenomination);
         if (!results.isEmpty()) {
            if (minLength==0 || (1+results.size()) < minConfig.size()) {               
               results.add(coin);
               minConfig=results;
               minLength=minConfig.size();
            }
         }
     }    
     lenChoices.put(value,minConfig);  
     return lenChoices.get(value);
  }
}

public static void main(String[] args) {
   System.out.println("enter the denoninations, hit enter to Zero(0) to finish");
   Scanner console = new Scanner(System.in);
   List<Integer> coinlist= new ArrayList<Integer>();
   int input = console.nextInt();
   while (input>0) {
      coinlist.add(input);
      input = console.nextInt();
   }
   System.out.println("coin collections are :"+ coinlist);
   System.out.println("enter the sum for which you need minimum coins");
   input = console.nextInt();
   MinCoinCollectionBacktrack result=new MinCoinCollectionBacktrack(input,coinlist);
   List<Integer> output = result.Mincoins();
   System.out.println("you require " + output.size() + " coins in the"
                                    + " following combination " + output);

 } 

} 

пожалуйста, не стесняйтесь комментировать потенциальные области улучшения стиля и алгоритма. Спасибо!