[
math
dfs
backtracking
]
Leetcode 0254 Factor Combinations
Problem statement
https://leetcode.com/problems/factor-combinations/
Solution
Add elements into factorization one by one, each time trying all elements $\geqslant$ than the last one.
Let us use function dfs(num, built)
, where nums
is number we still need to factorize and built
is already built sequence. Each time we check all numbers, starting with the biggest factor we have (if it is empty, start with 2
). Each time we need to go only until the square root, because if we go after, we can not take next factor. Also we need to consider the case, when we take the rest factor as one number. In the end we need to remove factorization of n = [n]
from final answer.
Complexity
It is difficult to say, I should say it is between $O(\sqrt{n})$ and $O(n)$.
Code
class Solution:
def getFactors(self, n):
self.ans = []
def dfs(num, built):
if num == 1:
self.ans.append(built)
return
start = max(2, built[-1]) if built else 2
for i in range(start, int(sqrt(num)) + 1):
if num % i == 0:
dfs(num//i, built + [i])
dfs(1, built + [num])
if n == 1: return []
dfs(n, [])
return self.ans[:-1]