Numbers can be regarded as product of its factors. For example,
8 = 2 x 2 x 2;
= 2 x 4.
Write a function that takes an integer n and return all possible combinations of its factors.
Note:
- You may assume that n is always positive.
- Factors should be greater than 1 and less than n.
Examples:
input: 1
output:
[]
input: 37
output:
[]
input: 12
output:
[
[2, 6],
[2, 2, 3],
[3, 4]
]
input: 32
output:
[
[2, 16],
[2, 2, 8],
[2, 2, 2, 4],
[2, 2, 2, 2, 2],
[2, 4, 4],
[4, 8]
]
解法一：
先求出所有的factor，在用DFS。注意由于答案中的factor都是升序排列，所以在往line里加入数字时先判断一下要加入line的数字是不是>=里面最后一个（如果有的话）。 或者先对factor.sort()，然后每次取得时候从 factors[i:]里面取，这样也可以保证每个解都是递增数列。
class Solution(object):
def getFactors(self, n):
"""
:type n: int
:rtype: List[List[int]]
"""
res = []
line = []
factors = []
for i in range(2,int(math.sqrt(n))+1):
if n%i == 0 and i< math.sqrt(n):
factors.append(i)
factors.append(n/i)
elif n == i*i:
factors.append(i)
if not factors:
return []
self.DFS(factors, n, res, line)
return res def DFS(self, nums, target, res, line):
if target == 1:
res.append([x for x in line])
return if target > 1:
for elem in nums:
if target % elem == 0 and (not line or line and elem >= line[-1]):
line.append(elem)
self.DFS(nums, target/elem, res, line)
line.pop()