All unique combinations to make change for a given amount

changeCombinations

using System;
using System.Collections.Generic;

namespace AllCombinationsForMakingChange
{
    public class Program
    {
        public static void Main(string[] args)
        {
            var amount = 8;
            int[] denoms = new int[]{1, 4, 6};
            Console.WriteLine("Different ways to make change for {0}", amount);
            var result = allCombinationsToMakeChange(amount, denoms);
            foreach (var list in result) {
                display(list);
            }
            
            Console.WriteLine("Minimum denoms need to make change for {0} is {1}",
                amount, getMinimumCoins(amount, denoms));
        }
        
        static void display(List<int> list) {
            foreach (var item in list) {
                Console.Write(item + " ");
            }
            
            Console.WriteLine();
        }
        
        static int getMinimumCoins(int amount, int[] denoms) {
            if (amount == 0 || denoms.Length == 0) {
                return 0;
            }
            
            int[] min_denoms_amount = new int[amount + 1];
            
            for (int amt = 1; amt < min_denoms_amount.Length; amt++) {
                int min_denoms = -1;
                
                foreach (var coin in denoms) {
                    if (coin <= amt) {
                        var remainder_amt = amt - coin;
                        
                        if (min_denoms_amount[remainder_amt] == -1) {
                            continue;
                        }
                        
                        var curr_denoms = 1 + min_denoms_amount[remainder_amt];
                        
                        if (min_denoms == -1 || (curr_denoms < min_denoms)) {
                            min_denoms = curr_denoms;
                        }
                    }
                }
                
                min_denoms_amount[amt] = min_denoms;
            }
            
            return min_denoms_amount[amount];
        }
        
        static List<List<int>> allCombinationsToMakeChange(int amount, int[] denoms) {
            var result = new List<List<int>>();
            
            if (amount == 0) {
                result.Add(new List<int>());    
            }
            
            for (int i = 0; i < denoms.Length; i++) {
                
                int newAmount = amount - denoms[i];
                               
                if (newAmount >= 0) {
                    
                    int[] newDenoms = new int[denoms.Length - i];
                    // Copies newDenoms.Length worth of elements
                    // starting at index i from denoms to newDenoms
                    Array.Copy(denoms, i, newDenoms, 0, newDenoms.Length); 
                    
                    var otherCombiations = allCombinationsToMakeChange(newAmount, newDenoms);
                    
                    foreach (var combination in otherCombiations) {
                        combination.Add(denoms[i]);
                        result.Add(combination);
                    }
                }
            }
            
            return result;
        }
    }
}