using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        foreach (var result in Decode("102131415161021314151610213141516"))

            Console.WriteLine(result);

    }

    public static IEnumerable<string> Decode(string encoded) {

        var memoizedResults = new Dictionary<string, List<string>>();

        return DecodeHelper("", encoded, memoizedResults);

    }

    public static IEnumerable<string> DecodeHelper(string decodedPrefix, string encoded, Dictionary<string, List<string>> memoizedResults)

    {       

        if  (memoizedResults.TryGetValue(encoded, out var decoded)) {

            foreach (var result in decoded)

                yield return result;

            yield break;

        }

        if (encoded.Length == 0) {

            yield return decodedPrefix;

            yield break;

        }

        if (TryDecodeLetter(encoded.Substring(0, 1), out var letter1)) {

            foreach (var result in DecodeHelper(decodedPrefix + letter1, encoded.Substring(1), memoizedResults))

                yield return result;

        }

        if (encoded.Length > 1 && TryDecodeLetter(encoded.Substring(0, 2), out var letter2)) {

            foreach (var result in DecodeHelper(decodedPrefix + letter2, encoded.Substring(2), memoizedResults))

                yield return result;

        }

    }

​

    private static bool TryDecodeLetter(string encoded, out string letter) {

        var value = Int32.Parse(encoded);

        if (value < 1 || value > 26) {

            letter = null;

            return false;

        } else {

            letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"[value - 1].ToString();

            return true;

        }

    }

}