Coins

coins

using System;
using System.Collections.Generic;
using System.Linq;

namespace MinimumCoins
{
    public class Program
    {
        public static void Main(string[] args)
        {
            test(new int[]{2, 3, 5}, 6);
            test(new int[]{3, 6, 9}, 18);
        }
        
        static void test(int[] denoms, int amount) {
            Console.WriteLine("Minimum number of coins needed to make change for {0} is {1}", amount, minimumCoins(denoms, amount));
            
            Console.WriteLine("Number of ways to make change for {0} is {1}", amount, waysToMakeChange(denoms, amount));
            
            var combinations = getChangeCombinations(denoms, amount);
            foreach(var comb in combinations) {
                foreach(var item in comb) {
                    Console.Write(item + " ");
                }
                Console.WriteLine();
            }
        }
        
        static int minimumCoins(int[] denoms, int amount) {
            
            int[] amounts = new int[amount + 1];
            amounts[0] = 0;
            
            for(int i = 1; i < amounts.Length; i++) {
                int minimum = Int32.MaxValue;
                foreach(var denom in denoms) {
                    if (denom <= i) {
                        var remainder = i - denom;
                        if (amounts[remainder] >= 0) {
                            int currentDenoms = 1 + amounts[i - denom];
                            minimum = Math.Min(currentDenoms, minimum);   
                        }
                    }
                }
                if (minimum != Int32.MaxValue) {
                    amounts[i] = minimum;
                } else {
                    amounts[i] = -1;
                }
            }
            
            return amounts[amount];
        }
        
        static int waysToMakeChange(int[] denoms, int amount) {
            
            int[] amounts = new int[amount + 1];
            amounts[0] = 1;
            
            foreach(var coin in denoms) {
                for(int i = coin; i < amounts.Length; i++) {
                    amounts[i] += amounts[i - coin];
                }
            }
            
            return amounts[amount];
        }
        
        static List<List<int>> getChangeCombinations(int[] denoms, int amount) {
            
            List<List<int>>[] amounts = new List<List<int>>[amount + 1];
            
            foreach(var coin in denoms) {
                for(int i = coin; i < amounts.Length; i++) {
                    
                    var remainder = i - coin;
                    
                    if (remainder == 0) {
                        if (amounts[i] == null) {
                            amounts[i] = new List<List<int>>();
                        }
                        var newComb = new List<int> { coin };
                        amounts[i].Add(newComb);
                    } else if (amounts[remainder] != null) {
                        
                        if (amounts[i] == null) {
                            amounts[i] = new List<List<int>>();
                        }
                        
                        var other = amounts[remainder];
                        
                        foreach(var list in other) {
                            var newComb = list.Select(x => x).ToList(); // Create a copy of the list
                            newComb.Add(coin);
                            amounts[i].Add(newComb);
                        }
                    }
                }
            }
            
            return amounts[amount];
        }
    }
}