0. Problem

We'll make a recursive function that visits every possible string we can interpret. It will go through and interpret each number in numbers left to right. This means the function needs to know what index it's up to. It also needs to know the the string of letters it's built so far.

1. Recursion

We want to consider all the possible letters that can be made from the current digit. For every possible digit we can add, we should add it and continue on the next index. Here's the recursion:

2. Base case

When we get to the end of the array, we should add the letters we have to the solution.

3. Code

Here's the full code. Just combine the recursion and the base case, and optimize by using Backtracking, which just means we make all our parameters into global variables.

Time Complexity $O(d \cdot 2^d)$, where $d$ is the length of numbers. We iterate through each possible string, which roughly $4^d$ entries in the answer. Each entry is of size $O(d)$. So creating the final output must take $d \cdot 2^d$ time. Another way to think of this is that there are $4^d$ entries we find, and each one spends $O(d)$ time running "".join(letters).

Space Complexity $O(d \cdot 2^d)$ for the output array. The Call Stack and global parameters also take up some space, but the output array's space complexity beats them by far.

Call Stack Complexity $O(d)$. The recursion gets up to $d$ calls deep, and each call uses $O(1)$ space.