Find all possible combinations of a String representation of a number

Assuming you only need to count the number of combinations.

Assuming 0 followed by an integer in [1,9] is not a valid concatenation, then a brute-force strategy would be:

Count(s,n)
    x=0
    if (s[n-1] is valid)
        x=Count(s,n-1)
    y=0
    if (s[n-2] concat s[n-1] is valid)
        y=Count(s,n-2)
    return x+y

A better strategy would be to use divide-and-conquer:

Count(s,start,n)
    if (len is even)
    {
        //split s into equal left and right part, total count is left count multiply right count
        x=Count(s,start,n/2) + Count(s,start+n/2,n/2);
        y=0;
        if (s[start+len/2-1] concat s[start+len/2] is valid)
        {
            //if middle two charaters concatenation is valid
            //count left of the middle two characters
            //count right of the middle two characters
            //multiply the two counts and add to existing count
            y=Count(s,start,len/2-1)*Count(s,start+len/2+1,len/2-1);
        }
        return x+y;
    }
    else
    {
        //there are three cases here:

        //case 1: if middle character is valid, 
        //then count everything to the left of the middle character, 
        //count everything to the right of the middle character,
        //multiply the two, assign to x
        x=...

        //case 2: if middle character concatenates the one to the left is valid, 
        //then count everything to the left of these two characters
        //count everything to the right of these two characters
        //multiply the two, assign to y
        y=...

        //case 3: if middle character concatenates the one to the right is valid, 
        //then count everything to the left of these two characters
        //count everything to the right of these two characters
        //multiply the two, assign to z
        z=...

        return x+y+z;
    }

The brute-force solution has time complexity of T(n)=T(n-1)+T(n-2)+O(1) which is exponential.

The divide-and-conquer solution has time complexity of T(n)=3T(n/2)+O(1) which is O(n**lg3).

Hope this is correct.

To just get the count, the dynamic programming approach is pretty straight-forward:

A[0] = 1
for i = 1:n
  A[i] = 0
  if input[i-1] > 0                            // avoid 0
    A[i] += A[i-1];
  if i > 1 &&                          // avoid index-out-of-bounds on i = 1
      10 <= (10*input[i-2] + input[i-1]) <= 26 // check that number is 10-26
    A[i] += A[i-2];

If you instead want to list all representations, dynamic programming isn't particularly well-suited for this, you're better off with a simple recursive algorithm.

First off, we need to find an intuitive way to enumerate all the possibilities. My simple construction, is given below.

 let us assume a simple way to represent your integer in string format.

   a1 a2 a3 a4 ....an, for instance in 121 a1 -> 1 a2 -> 2, a3 -> 1

Now,

We need to find out number of possibilities of placing a + sign in between two characters. + is to mean characters concatenation here.

a1 - a2 - a3 - .... - an, - shows the places where '+' can be placed. So, number of positions is n - 1, where n is the string length. 

Assume a position may or may not have a + symbol shall be represented as a bit. So, this boils down to how many different bit strings are possible with the length of n-1, which is clearly 2^(n-1). Now in order to enumerate the possibilities go through every bit string and place right + signs in respective positions to get every representations,

For your example, 121

   Four bit strings are possible 00 01 10 11
   1   2   1
   1   2 + 1
   1 + 2   1
   1 + 2 + 1

  And if you see a character followed by a +, just add the next char with the current one and do it sequentially to get the representation,

 x + y z a + b + c d

 would be (x+y) z (a+b+c) d  

Hope it helps.

And you will have to take care of edge cases where the size of some integer > 26, of course.

I think, recursive traverse through all possible combinations would do just fine:

mapping = {"1":"A", "2":"B", "3":"C", "4":"D", "5":"E", "6":"F", "7":"G", 
"8":"H", "9":"I", "10":"J", 
"11":"K", "12":"L", "13":"M", "14":"N", "15":"O", "16":"P", 
"17":"Q", "18":"R", "19":"S", "20":"T", "21":"U", "22":"V", "23":"W", 
"24":"A", "25":"Y", "26":"Z"}

def represent(A, B):
    if A == B == '':
        return [""]
    ret = []
    if A in mapping:
        ret += [mapping[A] + r for r in represent(B, '')]
    if len(A) > 1:
        ret += represent(A[:-1], A[-1]+B)
    return ret

print represent("121", "")