Почему это работает
- Вызов i выбирает букву для цифры i и передаёт остальное вызову i + 1, поэтому в дереве по уровню на цифру и по ветке на букву: каждое слово — один путь от корня до листа.
- Буква убирается, когда вызов вернулся, и освобождает место, поэтому следующая буква той же цифры пробуется с теми же буквами перед ней.
- Слово сохраняется, только когда i дошёл до конца, поэтому в нём всегда ровно по одной букве на цифру.
Сложность
Время O(n × 4ⁿ) для n цифр: до 4ⁿ слов, каждое склеивается за n шагов. Память O(n) помимо ответа: путь и стек вызовов глубиной n.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗