Numbers can be regarded as the product of their factors.
For example,
8 = 2 x 2 x 2 = 2 x 4
.Given an integer
n
, return all possible combinations of its factors. You may return the answer in any order.Note that the factors should be in the range
[2, n - 1]
.Example 1:
Input: n = 1
Output: []
Example 2:
Input: n = 12
Output: [[2,6],[3,4],[2,2,3]]
Example 3:
Input: n = 37
Output: []
Constraints:
1 <= n <= 10<sup>7</sup>
题目大意:
求所有因式分解
解题思路:
求所有解,所以用DFS。类似于LeetCode 039 Combination Sum元素可复用。
解题步骤:
N/A
注意事项:
- 类似于元素可复用的组合和。但更似全组合模板,append发生在循环中,而不是终止条件中。比如12,遇到2就把商[2, 6]加入到结果
- 数值区间的组合,start和target都是数值,而不是数组长度。i是从start开始,而不是从2开始,保证path里的数有序
- target // i < i 保证path里的数有序,否则12=232,不可行
- i从start循环到math.sqrt(n) + 1,否则会TLE
Python代码:
1 | def getFactors(self, n: int) -> List[List[int]]: |
算法分析:
时间复杂度为O(2n)
,空间复杂度O(# of prime factors)