CoinsCombinations2023

using System;
using System.Collections.Generic;

public class CoinCombinations
{
    private static readonly int[] Coins = { 1, 2, 5, 10, 20, 50 };
    private static readonly List<List<int>> Combinations = new List<List<int>>();

    public static void Main()
    {
        FindCombinations(new List<int>(), 100);
        foreach (var combination in Combinations)
        {
            Console.WriteLine(string.Join(" ", combination));
        }
    }

    public static void FindCombinations(List<int> currentCombination, int remaining)
    {
        if (remaining == 0)
        {
            Combinations.Add(new List<int>(currentCombination));
            return;
        }

        if (remaining < 0)
        {
            return;
        }

        for (int i = 0; i < Coins.Length; i++)
        {
            if (currentCombination.Count == 0 || Coins[i] >= currentCombination[currentCombination.Count - 1])
            {
                currentCombination.Add(Coins[i]);
                FindCombinations(currentCombination, remaining - Coins[i]);
                currentCombination.RemoveAt(currentCombination.Count - 1);
            }
        }
    }
}