#### Approach #1 Backtracking [Accepted]

**Intuition**

We need to find a way to build each string that will be added to our list of combinations such that we only add one character for every digit-to-character string mapping.

The above can be accomplished by using a backtracking approach.

**Algorithm**

First build a list of mappings from digits to characters. Next get all possible combinations of those mappings by adding one character at a time and recursively popping each mapping off of the queue.

**Python**

```
from collections import deque
class Solution(object):
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
maps = {
"2": "abc", "3": "def",
"4": "ghi", "5": "jkl",
"6": "mno", "7":"pqrs",
"8": "tuv", "9": "wxyz"
}
if "0" in digits or "1" in digits: return []
nMaps = deque([maps[d] for d in digits])
combos = set()
def getCombos(combo, nMaps):
if bool(nMaps) == False:
if bool(combo) and combo not in combos:
combos.add(combo)
return
m = nMaps.popleft()
for c in m:
getCombos(combo + c, nMaps)
nMaps.appendleft(m)
getCombos("", nMaps)
return list(combos)
```

**Complexity Analysis**

- Time complexity : O(\prod\limits_{i=1}^n A[d].length, d = digts[i])$$.

The generation of all the character combinations dominates the time-complexity. The number of number mappings is equal to the product of all digit-to-character mappings or $$A$$.

- Space complexity : $$O(\prod\limits_{i=1}^n digits.length * A[d].length, d = digts[i])$$.