In order to solve this problem, we want to write a recursion that visits every possible string we can interpret, given the original string of numbers numbers. We need to keep track of the current string of letters we've interpreted so far, which we'll call letters.

1. Recursion

As usual, we find the recursion by focusing on the first characters in the string. You can interpret the first character as a letter if it's between "1", and "9", or you can interpret the first two characters as a letter if they're between "10" and "26". Here's the recursion for this:

It's slow to recurse on the numbers string like this, since strings are immutable, and every time you add/remove a letter you create a whole new string. You can fix this by recursing on the index i in the string, instead of on the full string itself. We'll also use Backtracking and make the letters input into a global array so that you can append and pop from it quickly. We'll also make the index i into a global parameter, but this isn't needed.

2. Base case

When the whole string has been interpreted, we know we have a solution. This happens when i is at the end of the string. In this case, we should add the current interpretation that we have letters as one of the answers to the problem.

3. Code

Here's the code you get, combining the recursion and base case:

Time Complexity $O(\texttt{n} \cdot 2^\texttt{n})$. There are $O(2^\texttt{n})$ entries in the final array, and each entry is of size $O(\texttt{n})$, where n is the size of the input.

Space Complexity $O(\texttt{n} \cdot 2^\texttt{n})$ for the answer array. The Call Stack gets to size $O(\texttt{n})$ and letters does too, but both of these are negligible compared to the answer array.