**Description:**

Given a string containing digits from `2`

to `9`

inclusive, return all possible letter combinations that the number could represent. Return the answer in **any order**.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Digit | Letters |
---|---|

2 | “abc” |

3 | “def” |

4 | “ghi” |

5 | “jkl” |

6 | “mno” |

7 | “pqrs” |

8 | “tuv” |

9 | “wxyz” |

### Example 1:

```
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
```

### Example 2:

```
Input: digits = ""
Output: []
```

### Example 3:

```
Input: digits = "2"
Output: ["a","b","c"]
```

### Analysis:

This problem is essentially generating all possible combinations from the digit-to-letter mappings. Each digit can be mapped to 3-4 possible letters, and the goal is to generate all possible combinations using the provided digits.

To solve this problem, a recursive backtracking approach can be used. Starting from the first digit, we explore all possible letter choices, and then proceed to the next digit, combining the choices until we have generated all combinations.

### Python Code:

```
def letterCombinations(digits: str):
# Mapping of digits to corresponding letters
phone_map = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz'
}
# If the input is empty, return an empty list
if not digits:
return []
# List to store the result combinations
result = []
# Backtracking function to generate combinations
def backtrack(index, current_combination):
# If the current combination is as long as the digits, add it to the results
if index == len(digits):
result.append(current_combination)
return
# Get the letters corresponding to the current digit
current_digit = digits[index]
letters = phone_map[current_digit]
# Recursively generate all combinations
for letter in letters:
backtrack(index + 1, current_combination + letter)
# Start the backtracking with an empty combination
backtrack(0, "")
return result
```

### Example usage:

```
print(letterCombinations("23"))
# Output: ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
```

### Time Complexity:

The time complexity of the solution is **O(3^n × 4^m)**, where:

`n`

is the number of digits that map to 3 letters (`2`

,`3`

,`4`

,`5`

,`6`

,`8`

).`m`

is the number of digits that map to 4 letters (`7`

,`9`

).

In the worst case, if all the digits map to 4 letters (like ‘7’ and ‘9’), there would be `4^m`

combinations to explore. However, since most digits map to 3 letters, the complexity varies based on the actual input. Therefore, a loose upper bound is **O(4^n)** where `n`

is the length of the digits string.

### Space Complexity:

- The space complexity is
**O(n)**for storing the recursion stack, where`n`

is the length of the input digits. - Additionally, the space required to store the result list is
**O(4^n)**, where`n`

is the length of the digits, as each combination is stored in the result.