LeetCode 254 Factor Combinations

LeetCode

<div>

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:

<pre>Input: n = 1 Output: [] </pre>

Example 2:

<pre>Input: n = 12 Output: [[2,6],[3,4],[2,2,3]] </pre>

Example 3:

<pre>Input: n = 37 Output: [] </pre>

Constraints:

• 1 <= n <= 10<sup>7</sup>

</div>

题目大意：

求所有因式分解

解题思路：

求所有解，所以用DFS。类似于LeetCode 039 Combination Sum元素可复用。

解题步骤：

N/A

注意事项：

1. 类似于元素可复用的组合和。但更似全组合模板，append发生在循环中，而不是终止条件中。比如12，遇到2就把商[2, 6]加入到结果
2. 数值区间的组合，start和target都是数值，而不是数组长度。i是从start开始，而不是从2开始，保证path里的数有序
3. target // i < i 保证path里的数有序，否则12=232，不可行
4. i从start循环到math.sqrt(n) + 1，否则会TLE

Python代码：

def getFactors(self, n: int) -> List[List[int]]:
	res = []
	self.dfs(n, 2, n, [], res)
	return res

def dfs(self, n, start, target, path, res):
	if target == 1:
		return
	for i in range(start, int(math.sqrt(n) + 1)): # remember to use start
		if target % i != 0 or target // i < i: # remember
			continue
		path.append(i)
		res.append(list(path + [target // i]))
		self.dfs(n, i, target // i, path, res) 
		path.pop()

算法分析：

时间复杂度为<code>O(2ⁿ)</code>，空间复杂度O(# of prime factors)