**Note:** I have also figured out a more efficient and simple backtracking algorithm with only 99ms in Python. Please check backtracking solution, where C++ and Python implementions are provided.

We test every possible `(m,n)`

such that `a=m*n`

. Then we get a solution `s`

by concatenating `m`

and `n`

. However, `m`

and `n`

may themselves have multiple digits, which require further factorization. Therefore, a recursive method is used. After we get all the possible `s`

, return the minimum one.

Note that in this recursive tree, we may encounter the **same** number for factorization. Therefore, a ** memoization** trick is adopted to form a dynamic programming method.

```
class Solution(object):
def smallestFactorization(self, a):
"""
:type a: int
:rtype: int
"""
self.memory = {} # memory[k] is the Minimum Factorization of k
return self.dp(a)
def dp(self, k):
if k < 10:
return k
if k in self.memory:
return self.memory[k]
# here we test every possible factorization of k into k = m * n
# and find the minumum integer composed of m and n if any
s = int(math.sqrt(k))
factorizations = []
for m in range(s, 1, -1):
if k % m == 0:
n = k // m
left = self.dp(m)
right = self.dp(n)
if left != 0 and right != 0: # only m and n both have answers
d = 0 # find the number of digits of right
t = right
while t > 0:
d += 1
t = t // 10
r = left * 10 ** d + right # for example, 123 and 247 => 123247
if r <= 2**31 - 1: # fit in 32-bit signed integer
factorizations.append(r)
if factorizations: # if we have found any legal solution
self.memory[k] = min(factorizations)
else:
self.memory[k] = 0
return self.memory[k]
```