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]