# 因式分解

描述

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

```
````


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nataliekung.gitbook.io/ladder_code/l9tu-he-sou-suo/yin-shi-fen-jie.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.