# Easy-to-understand backtracking solution. Python and C++.

• Backtracking

Assume a factorization is a series of `m` digits and the value represented by the first `k-1` digits is called `pre_val` while the multiplication of the first `k-1` 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 non-zero 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` and `pre_val` can fit into a signed integer, i.e., we have found a legal solution.

• list itemIf there exists no such `d` to make `pre_mul*d` a factor of `a`

``````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, ``48`can be factorized into`68`and`86`and 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.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.