class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        # Check for an empty input
        if not digits:
            return []

        # Mapping of digits to letters
        phone_map = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }

        def backtrack(index: int, path: [str]):
            # If the path's length equals digits' length, add the combination to the result
            if len(path) == len(digits):
                combinations.append("".join(path))
                return

            # Iterate through the letters of the current digit
            for letter in phone_map[digits[index]]:
                path.append(letter)  # Add letter to the current path
                backtrack(index + 1, path)  # Backtrack with the next digit
                path.pop()  # Remove the letter to try the next one

        combinations = []  # Initialize the combinations list
        backtrack(0, [])  # Start backtracking from the first digit
        return combinations