Solución del problema de los Lucky Tickets

Entre muchas aficiones que tengo, una de ellas es resolver problemas de algoritmia. Soy usuario activo de jurados en línea que no son mas que sitios con bancos de problemas en los cuales el usuario puede registrarse y enviar sus soluciones para que un evaluador automático las califique y de esa forma poder competir con programadores de todo el mundo.

A pesar de haber resuelto mucho ejercicios de este tipo, a menudo me encuentro con que a pesar de haber pasado mucho tiempo pensando en una solución y finalmente de haberla encontrado, al poco tiempo no la recuerdo. Es por esto que me he propuesto la meta de publicar aquí cada solución que envié con una breve explicación de manera que el algoritmo quede descrito para el futuro.

En esta ocasión he resuelto el problema de los Lucky Tickets en lenguaje C#.

using System;
using System.Collections;

class Program
    {
        static void Main(string[] args)
        {
            int x = int.Parse(Console.ReadLine());
            Ticket(x);
         }
        public static void Ticket(int cifras)
        {
            int mitad = cifras / 2;
            int result = 0;
         
            for (int i = 0; i <= 9 * mitad; i++)
            {
                int sum=SumanK(i,mitad);
                result += sum * sum;
            }
            Console.WriteLine(result);
        }

        private static int SumanK(int k, int cifras)
        {
            if (cifras == 1 && k<10)
            {
                return 1;
            }
            int min = Math.Min(k, 9);
            int max = Math.Max(0, k - 9 * (cifras - 1));
            int count = 0;

            for (int i = max; i <= min; i++)
            {
                count=count+SumanK(k - i, cifras - 1);  
            }
            return count;
        }     
    }
Solución:
La solución puede dividirse en 2 partes muy simples. La primera es detectar cuantas distintas sumas existen donde los sumandos sean los dígitos de números de n/2 cifras. De esta forma para por ejemplo n=6, n/2=3--> 9*9*9=27. Las posibles sumas de los dígitos de números de 3 dígitos vas desde 0 hasta 27.

Dicho, esto solo tendríamos que encontrar para cada uno de estos valores de posible suma, que combinaciones de digitos hacen que se pueda obtener la misma. Para esto se usa el algoritmo recursivo implementado mediante la función SumanK, que funciona de esta forma:

Dadas la cantidad de cifras c y el numero a obtener como suma k:

• Si c=1 y k<10 se devuelve 1
• Si c>1 
• El mínimo dígito posible para la ultima posición sería el Máximo entre 0 y k-9*Todos los dígitos restantes
• El máximo dígito posible sería el mínimo entre k y 9
• Iterando desde mínimo hasta máximo (valor i) y se calcula recursivamente cuantos números suman k-i y tienen una cifra menos.