Комбинации

На клавиатуре старых мобильных телефонов каждой цифре соответствовало несколько букв. Примерно так:

2:’abc’,
3:’def’,
4:’ghi’,
5:’jkl’,
6:’mno’,
7:’pqrs’,
8:’tuv’,
9:’wxyz’

Вам известно в каком порядке были нажаты кнопки телефона, без учета повторов. Напечатайте все комбинации букв, которые можно набрать такой последовательностью нажатий.

Формат ввода

На вход подается строка, состоящая из цифр 2-9 включительно. Длина строки не превосходит 10 символов.

Формат вывода

Выведите все возможные комбинации букв через пробел.

def letterCombinations(digits):

    letters = {'2':'abc', '3':'def','4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs','8':'tuv', '9':'wxyz'}

    def backtrack(digits, path, res):
        if digits == '':
            res.append(path)
            return
        for letter in letters[digits[0]]:

            path += letter
            backtrack(digits[1:], path, res)
            path = path[:-1]
    res = []
    backtrack(digits, '', res)
    for x in res:
        print(x, end=' ')

vvod = (input())
letterCombinations(vvod)