Backtracking
Assume a factorization is a series of m
digits and the value represented by the first k1
digits is called pre_val
while the multiplication of the first k1
digits is pre_mul
. Then at the k^th
step we need to choose another digit d
from 2 to 9 (1 is useless). A nonzero digit d
can be chosen if it satisfies that pre_mul*d
can divide a
. Then we test all such d
s to get all possible factorization by backtracking. Finally, return the minimum one.
Termination conditions

If
pre_val
is greater than the max signed integer 
list itemIf
pre_mul=a
andpre_val
can fit into a signed integer, i.e., we have found a legal solution. 
list itemIf there exists no such
d
to makepre_mul*d
a factor ofa
class Solution(object):
def smallestFactorization(self, a):
"""
:type a: int
:rtype: int
"""
if a < 10:
return a
self.a = a
self.solutions = []
self.backtrack(0, 1)
return min(self.solutions) if self.solutions else 0
def backtrack(self, pre_val, pre_mul):
# check termination condition
if pre_val > 2**31  1:
return
if pre_mul == self.a:
self.solutions.append(pre_val)
return
# choose the next digit
for d in range(2, 10):
current_mul = pre_mul * d
if self.a % current_mul == 0:
current_val = pre_val * 10 + d
self.backtrack(current_val, current_mul)
However, due to the insufficiency of recursion on LeetCode, this backtracking will lead to TLE. (I have encountered TLE multiple times when using backtracking in Python. Simply translate it into C++ and it will be accepted.)
Then we rewrite the program in C++ and it is accepted with 403ms.
#include <limits>
class Solution {
public:
int smallestFactorization(int a) {
if (a < 10)
return a;
std::vector<int> solutions;
backtrack(0, 1, solutions, a);
if (solutions.empty())
return 0;
else
return *std::min_element(solutions.cbegin(), solutions.cend());
}
void backtrack(long long pre_val, long long pre_mul, std::vector<int>& solutions, int a) {
// check termination conditions
if (pre_val > std::numeric_limits<int>::max())
return;
if (pre_mul == a) {
solutions.push_back((int)pre_val);
return;
}
// choose the next digit
for (int d = 2; d < 10; d++) {
auto current_mul = pre_mul * d;
if (a % current_mul == 0) {
auto current_val = pre_val * 10 + d;
backtrack(current_val, current_mul, solutions, a);
}
}
}
};
Now we try to improve the above Python backtracking algorithm to avoid TLE. It is noted that at each step we should choose a digit d
not less than the previous digit since we want to find the minimum solution. For example, ``48can be factorized into
68and
86and we will just keep
68```. That is to say, each factorization series is still legal after random permutation and we keep the one whose digits appear in ascending order.
With this improvement, the Python backtracking also passes the tests with only 99 ms.
class Solution(object):
def smallestFactorization(self, a):
"""
:type a: int
:rtype: int
"""
if a < 10:
return a
self.a = a
self.solutions = []
self.backtrack(0, 1, 2)
return min(self.solutions) if self.solutions else 0
def backtrack(self, pre_val, pre_mul, pre_d):
# check termination condition
if pre_val > 2**31  1:
return
if pre_mul == self.a:
self.solutions.append(pre_val)
return
# choose the next digit
for d in range(pre_d, 10):
current_mul = pre_mul * d
if self.a % current_mul == 0:
current_val = pre_val * 10 + d
self.backtrack(current_val, current_mul, d)
I have also provided a dynamic programming solution at dynamic programming solution.