Find all possible interpretations of an array of digits
test4 makes no sense. The question states "Given an array of digits (1 to 9) as input...", yet your test input is {12, 23, 2}.



As the digits are 1-9, there's no way to represent 'j' (10) or 't' (20). I'm guessing that's a mistake in the question.




  I'm also verifying space complexity to be \$O(2^n)\$


\$O(2^n)\$ is certainly an upper bound on the number of valid interpretations, but we can find a tighter bound.

Here's a hint: let's look at the number of interpretations of this sequence of inputs

{ }               1
{ 1 }             1
{ 1, 1 }          2
{ 1, 1, 1 }       3
{ 1, 1, 1, 1 }    5
...


Look familiar? I'm going to re-post part of an another answer of mine.

Suppose our array \$s = s_0 s_1 \ldots s_{n - 1}\$ is of length \$n\$. We define a function \$f\$ such that \$f(i)\$ is the number of ways to interpret the suffix of \$s\$ starting at position \$i\$: \$s_i s_{i + 1} \ldots s_{n - 1}\$. In this way, our final solution will be the value of \$f(0)\$.

How many ways are there to interpret the empty array? Just one, so we can write

\begin{align}
f(n) &amp;= 1.
\end{align}

Now how about the suffix \$s_{n - 1}\$? Well if it's \$0\$, that's invalid; otherwise there's just one way to interpret it.

\begin{align}
f(n - 1) &amp;= \begin{cases}
0 &amp;\mbox{if } s_{n - 1} = 0, \\ 
1 &amp; \mbox{otherwise}. \end{cases}
\end{align}

Now for the general case, the suffix \$s_i s_{i + 1} \ldots s_{n - 1}\$.

If \$s_i = 0\$, there are no interpretations. Otherwise, we have two cases to deal with.

If \$10 \leq s_i s_{i + 1} \leq 26\$, we can interpret the suffix as

\begin{align}
(s_i s_{i + 1}) \underbrace{s_{i + 2} \ldots s_{n - 1}}_{f(i + 2) \text{ interpretations}} \quad \mbox{ or } \quad 
(s_i) \underbrace{s_{i + 1} s_{i + 2} \ldots s_{n - 1}}_{f(i + 1) \text{ interpretations}}.
\end{align}

Otherwise, we can only interpret the suffix as
\begin{align}
&amp;(s_i) \underbrace{s_{i + 1} s_{i + 2} \ldots s_{n - 1}}_{f(i + 1) \text{ interpretations}}.
\end{align}

Putting that all together, we get
\begin{align}
f(i) &amp;= \begin{cases}
0 &amp;\mbox{if } s_{i} = 0, \\
f(i + 1) + f(i + 2) &amp; \mbox{if } s_i = 1 \mbox{ or } (s_i = 2 \mbox{ and } s_{i + 1} \leq 6), \\
f(i + 1) &amp; \mbox{otherwise.}
\end{cases}
\end{align}

So in the worst case, for example { 1, 1, 1, ..., 1 }, this reduces to the \$n\$th Fibonacci number, giving us space complexity \$O(F_n)\$.