lintcode652 factorization

题目描述

给定一个n，求它的因式分解的所有组合。

思路

从2到sqrt(n)枚举，设当前的值为i，如果i能被n整除，剩下的n//i，一定可以作为当前的组合的最后一个元素，那么第一种组合确定。
以剩下的n//i作为新的n，从i开枚举，枚举到sqrt(n)，重复上面的过程。

复杂度

时间复杂度：O(nlogn)
空间复杂度：O(n)

代码

from typing import (
    List,
)
import math 
class Solution:
    """
    @param n: An integer
    @return: a list of combination
             we will sort your return value in output
    """
    def get_factors(self, n: int) -> List[List[int]]:
        # write your code here
        ans = []
        def dfs(n, f, res):
            if res:
                res.append(int(n))
                ans.append(res[:])
                res.pop()
            for i in range(f, int(math.sqrt(n))+1):
                if n%i == 0:
                    res.append(int(i))
                    dfs(n/i, i, res)
                    res.pop()
        dfs(n, 2, [])
        return ans 



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28