using System;

using System.Collections.Generic;

using System.Diagnostics;

using System.Linq;

public class Program {

    static readonly int[] _Numbers = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    public void Main() {

        int digits = 2;

        int sum = 8;

        bool verifyResults = true;

        RunSolution(Solution1, digits, sum, verifyResults);

    }

​

    void RunSolution(Func<int, int, bool, (int, List<int>)> solution, int digits, int sum, bool verifyResults) {

        if (sum > digits * 9) {

            throw new InvalidOperationException("The value of sum is too high for the number of digits.");

        }

​

        Stopwatch stopWatch = new Stopwatch();

        stopWatch.Start();

        (int count, List<int> results) = solution(digits, sum, verifyResults);

        stopWatch.Stop();

​

        Console.WriteLine($"Found {count} results in {stopWatch.Elapsed}");

        Console.WriteLine($"    Result: {string.Join(", ", results.Select(x => x.ToString("#,##0") + ":" + SumDigits(x)))}");

​

        //String.Join(", ", results).Dump();

​

        //if (verifyResults && results.Any(r => SumOfDigits(r) != sum)) {

        //    Console.WriteLine("One or more results are wrong.");

        //}

    }

​

    /// <summary>

    /// Return all x-digit numbers whose sum equals target sum

    /// </summary>

    /// <param name="digits">Number of digits</param>

    /// <param name="sum">Target sum</param>

    /// <param name="returnResults"></param>

    /// <returns></returns>

    (int count, List<int> results) Solution1(int digits, int sum, bool returnResults) {

        int count = 0;

        List<int> result = new List<int>();

​

        // Get combinations with repetition for desired number of digits

        int[][] combinationsWithRepetition = GetCombinationsWithRepetition(digits);

        // Go through each combination and determine if the sum equals target sum

        for (int i = 0; i < combinationsWithRepetition.Length; i++) {

            int[] n = combinationsWithRepetition[i];

            int t_sum = 0;

            bool allAreEqual = true;

            for (int j = 0; j < n.Length; j++) {

                int d = n[j];

                t_sum += d;

                // exit loop if sum has surpassed target sum

                if (t_sum > sum) {

                    break;

                }

                // check if all digits are equal; later used in canReverse

                if (allAreEqual && d != n[0]) {

                    allAreEqual = false;

                }

            }

            // we should not reverse "palindrome" numbers, nor numbers that start with zero

            bool canReverse = allAreEqual == false && n[0] != 0;

            // if ombination sum equals target sum add to count and results

            if (t_sum == sum) {

                // add to count

                count++;

                if (canReverse) {

                    // add to count if can reverse

                    count++;

                }

                // add to results if so desired

                if (returnResults) {

                    // add result 

                    result.Add(ConvertIntArrayToNumber(n, -1));

                    if (canReverse) {

                        // add reversed result if can reverse

                        result.Add(ConvertIntArrayToNumber(n, 1));

                    }

                }

            }

        }

        if (returnResults) {

            result = result.OrderBy(x => x).ToList();

        }

​

        return (count, result);

    }

​

    /// <summary>

    /// Get combination of digits for given number of digits

    /// </summary>

    /// <param name="digits">number of digits</param>

    /// <returns></returns>

    static int[][] GetCombinationsWithRepetition(int digits) {

        if (digits == 1) return _Numbers.Select(t => new int[] { t }).ToArray();

        return GetCombinationsWithRepetition(digits - 1)

            .SelectMany(t => _Numbers.Where(o => o.CompareTo(t.Last()) >= 0),

                (t1, t2) => t1.Concat(new int[] { t2 }).ToArray()).ToArray();

    }

​

    /// <summary>

    /// Convert an array of integers into an integer

    /// E.g. { 1, 2, 3, 4} => 1234 (forwards) or 4321 (backwards)

    /// </summary>

    /// <param name="input">array of integers</param>

    /// <param name="step">direction to iterate (-1: backwards; 1: forwards)</param>

    /// <returns></returns>

    static int ConvertIntArrayToNumber(int[] input, int step) {

        if (input == null) {

            throw new InvalidOperationException("Input is cannot be null");

        }

        if (!(step == -1 || step == 1)) {

            throw new InvalidOperationException("Step must 1 or -1");

        }

        int result = 0;

        for (int i = step < 0 ? input.Length - 1 : 0; step < 0 ? i >= 0 : i < input.Length; i += step) {

            result *= 10;

            result += input[i];

        }

        return result;

    }

​

    /// <summary>

    /// Get the sum of the digits of an integer

    /// </summary>

    /// <param name="input"></param>

    /// <returns></returns>

    static int SumDigits(int input) {

        int result = 0;

        string s = input.ToString();

        for (int i = 0; i < s.Length; i++) {

            char c = s[i];

            result += Convert.ToInt32(c.ToString());

        }

        return result;

    }

}