因式分解

https://www.lintcode.com/problem/652/?utm_source=sc-cheatsheet-cyc

描述

一个非负数可以被视为其因数的乘积。编写一个函数来返回整数 n 的因数所有可能组合。

• 组合中的元素(a1,a2,...,ak)必须是非降序。(即，a1≤a2≤...≤ak)。

• 结果集中不能包含重复的组合。

样例

样例1

输入：8输出： [[2,2,2],[2,4]]解释： 8 = 2 x 2 x 2 = 2 x 4

样例2

输入：1 输出： []

解题思路

算法：DFS

从2到sqrt(n)枚举因子，若存在一个数是n的因子，则继续从这个数到sqrt(n)枚举因子

• 从2开始搜，若当前数是n的因子，则加入当前因子队列

• 继续搜下一个大于当前因子的因子

• 当前组合搜完继续由下一个更大的因子开始搜

复杂度分析

• 时间复杂度O(nlog(n))

  • dfs搜索

• 空间复杂度O(n)

  • 记录所有因子组合

```python
from typing import (
    List,
)

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
        res = []
        self.dfs(n,2,[],res)
        return res

    def dfs(self, n, next_factor, path, res): #此处N不断减少，next_factor是当前status，从当前可行的路径直到sqrt(n）遍历下去。
        if len(path): #把最后一个元素加上，空队列不能作为结果
            path.append(int(n))
            res.append(path[:])
            path.pop()

        for i in range(next_factor,math.floor(math.sqrt(n)+1)): #这里起点是next_factor， 不是2.
            if n%i == 0:
                path.append(i)
                self.dfs(n/i, i, path, res)
                path.pop()
        

```