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: worst case, Space: for recursion depth.