Permutations

using System.Collections.Generic;

class Program
{
    static Dictionary<int, string> digitToChars =
        new Dictionary<int, string>
            { { 0, "0"},
                { 1, "1"},
                { 2, "ABC"},
                { 3, "DEF"},
                { 4, "GHI"},
                { 5, "JKL"},
                { 6, "MNO"},
                { 7, "PQRS"},
                { 8, "TUV"},
                { 9, "WXYZ"}
            };

    static IEnumerable<string> PermuteDigitsRec(string digits)
    {
        if (digits.Length == 0)
        {
            yield return "";
            yield break;
        }
        var n = digits[0] - '0';
        var tail = digits.Substring(1);
        var chars = digitToChars[n];
        foreach (var s in PermuteDigitsRec(tail))
        {
            foreach (var c in chars)
            {
                yield return c + s;
            }
        }
    }

    static string[] PermuteDigits(string digits)
    {
        var words = new List<string>();
        words.Add("");
        foreach (var digit in digits)
        {
            List<string> previous = words;
            words = new List<string>();
            int n = digit - '0';
            foreach (var c in digitToChars[n])
            {
                foreach(var word in previous)
                {
                    words.Add(word+c);
                }
            }
        }
        return words.ToArray();
    }

    static void Main(string[] args)
    {
        var words = PermuteDigits("3663");
        foreach(var x in words) System.Diagnostics.Debug.WriteLine(x);
    }
}