leetcode：254. 因子的组合【经典递归 + 新型递归 + 所有可能的因数分解】

题目截图

题目分析

• 不能选到1和n
• 可以考虑因子递增
• 对于cur，我们可以分为i和n // i 不妨 i < n // i
• 这样的话，我们可以按住i不动，继续分n // i 而且只分一些大于等于i的因子出来，这样就可以有效地去重
• 这里需要注意是嵌套，假设我们最终dfs返回的是res:list嵌套list，这样我们在看dfs(n // i, i)的时候，可以拿出里面的每个sub，然后把它和[i]连起来，再统一作为外层的res输出即可

ac code

class Solution:
    def getFactors(self, n: int) -> List[List[int]]:
        @cache
        def dfs(cur, lower):
            res = []
            for i in range(lower, int(sqrt(cur)) + 1):
                if cur % i == 0:
                    res.append([i, cur // i])
                    for sub in dfs(cur // i, i): # 保持不减，防止重复
                        res.append(sub + [i])
            return res
        
        return dfs(n, 2) # 从2开始
1
2
3
4
5
6
7
8
9
10
11
12
13

总结

• for sub in dfs(cur // i, i)这句话几乎没碰到过，有意思！
• 再给我写一次，我也不一定会写