Find all possible interpretations of an array of digits Consider a coding system for alphabets to integers where 'a' is
  represented as 1, 'b' as 2, .. 'z' as 26. Given an array of digits (1
  to 9) as input, write a function that prints all valid interpretations
  of input array.
  
  
    Input: {1, 1} Output: ("aa", 'k")  [2 interpretations: aa(1, 1), k(11)]
    
    Input: {1, 2, 1} Output: ("aba", "au", "la")  [3 interpretations: aba(1,2,1), au(1,21), la(12,1)]
    
    Input: {9, 1, 8} Output: {"iah", "ir"}  [2 interpretations: iah(9,1,8), ir(9,18)]
  


I'm looking for code-review, optimizations and best practices.  I'm also verifying space complexity to be \$O(2^n)\$, where \$n\$ is the number of alphabets is the length of input array.

public final class FormulateAlphabets {

    private static final String[] data = {
        "", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n",
        "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"
    };

    private FormulateAlphabets() { }

    public static List&lt;String&gt; getAllStrings(int[] arr) {

        List&lt;String&gt; strList = new ArrayList&lt;&gt;();
        formulate(arr, 0,  false, strList, new StringBuffer());
        formulate(arr, 0,  true,  strList, new StringBuffer()); 

        return strList;
    }


    private static void formulate(int[] arr, int currPosition, boolean includeNextPosition, List&lt;String&gt; strlist, StringBuffer sb) {

        int nextPosition = 0;

        if (!includeNextPosition) {
            sb.append(data[arr[currPosition]]);
            nextPosition = currPosition + 1;
        } else {

            if ((currPosition + 1) == arr.length) return;

            int result = arr[currPosition] * 10 + arr[currPosition + 1];
            if (result &lt;= 26) {
                sb.append(data[result]);
            } else {
                return;
            }

            nextPosition = currPosition + 2;
        }


        if (nextPosition == arr.length) {
            if (sb.length() &gt; 0) {
                strlist.add(sb.toString());
                sb.deleteCharAt(sb.length()-1);
            }
            return;
        }

        formulate(arr, nextPosition, false, strlist, sb);
        formulate(arr, nextPosition, true, strlist, sb);

        if (sb.length() &gt; 0) {
            sb.deleteCharAt(sb.length()-1);
        }
    }

}

public class FormulateAlphabetTests {

    @Test 
    public void test1() {
        int[] a1 = {1, 2, 3, 4};        
        assertEquals(Arrays.asList("abcd", "awd", "lcd"), FormulateAlphabets.getAllStrings(a1));
    }

    @Test 
    public void test2() {
        int[] a2 = {1, 2, 2, 1};  
        assertEquals(Arrays.asList("abba", "abu", "ava", "lba", "lu"), FormulateAlphabets.getAllStrings(a2));
    }

    @Test 
    public void test3() {
        int[] a3 = {1, 2, 3};
        assertEquals(Arrays.asList("abc", "aw", "lc"), FormulateAlphabets.getAllStrings(a3));
    }

    @Test 
    public void test4() {
        int[] a4 = {12, 23, 2};
        assertEquals(Arrays.asList("lwb"), FormulateAlphabets.getAllStrings(a4));
    }
}
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)\$.