##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
(Exponential in worst case)
Each digit has 3-4 letters. Worst case: all digits are 7 or 9 (4 letters each). If input has n digits, you generate up to 4^n combinations.
Time complexity: O(4^n). Space: O(n) for recursion depth, plus O(4^n) to store all results.
Counting told you this would be exponential. The product rule predicted it before you wrote any code.
