> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/l9tu-he-sou-suo/yin-shi-fen-jie.md).

# 因式分解

描述

一个非负数可以被视为其因数的乘积。编写一个函数来返回整数 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()
        

```
````