Letter Combinations - Implementation

Here's the full solution using backtracking:

function letterCombinations(digits)
    if digits is empty then
        return []
    phone := map where
        '2' → 'abc', '3' → 'def', '4' → 'ghi'
        '5' → 'jkl', '6' → 'mno', '7' → 'pqrs'
        '8' → 'tuv', '9' → 'wxyz'
    result := empty list
    path := empty list

    function backtrack(index)
        if index = length of digits then
            result.append(join path as string)
            return
        for each letter in phone[digits[index]]
            path.append(letter)
            backtrack(index + 1)
            path.pop()

    backtrack(0)
    return result

You try each letter for each digit, recursing to the next digit. When you process all digits, you add the combination. Time: $O(4^n)$ worst case, Space: $O(n)$ for recursion depth.