The problem

I am given a string of possible digits 2 through 9. These digits are mapped to letters, like an old T9 cell phone, and I need to return all possible letter combinations that the digits can produce.

I've looking into this problem for long enough to recognize that I need to make a hash map of numbers to letter arrays, and then use a recursive backtracking algorithm to generate all the combinations. I don't yet understand what said recursive backtracking algorithm is supposed to do - specifically.

The Solution

This is solved with a recursive function that starts at the first digit and walks through all options using depth first traversal.

In plain English, the function is recursively called until it finds a solution - the base case - adds the solution to our results array and returns, ending the recursion.

We start by passing in an empty array - indicating that we have no pieces of the solution yet - and 0 index, telling the algorithm to start at the first number passed in. We bypass the base case, as our empty array is shorter than the length of our input (unless our input is an empty string, which I guess is possible). Then, we identify the digit we're working with via the index passed into the function, and from there get the letters associated with that digit. Finally, we loop through all the letters, and pass each our existing input array with each new letter into the recursive function with the next index - continuing the cycle until each branch hits the expected input length.

function letterCombinations(digits: string): string[] {
    const digitsMap = {
        '2': ['a', 'b', 'c'],
        '3': ['d', 'e', 'f'],
        '4': ['g', 'h', 'i'],
        '5': ['j', 'k', 'l'],
        '6': ['m', 'n', 'o'],
        '7': ['p', 'q', 'r', 's'],
        '8': ['t', 'u', 'v'],
        '9': ['w', 'x', 'y', 'z'],
    }

    const result = [];

    const backtrack = (combo: string[], index: number) => {
        if(index === digits.length){
            result.push(combo.join(""));
            return;
        }

        const currentDigit = digits[index];
        const letters = digitsMap[currentDigit]
        for (const letter of letters){
            backtrack([...combo, letter], index + 1);
        }
    }
          backtrack([], 0);
         return result
};

Final thoughts

I find this algorithm to be quite elegant, once I got my head around it. Onto the next!