254. Factor Combinations
- Total Accepted: 16019
- Total Submissions: 40853
- Difficulty: Medium
- Contributors: Admin
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] ]
Code
import math
class Solution(object):
def getFactors(self, n):
"""
:type n: int
:rtype: List[List[int]]
"""
if n <= 1:
return []
res = []
self.helper(n, 2, [], res)
return res
def helper(self, target, start_num, factors, res):
if factors:
res.append(list(factors)+[target])
# only need to traverse until floor(sqrt(target))
for i in xrange(start_num, int(math.sqrt(target))+1):
if target % i == 0:
factors.append(i)
self.helper(target/i, i, factors, res)
factors.pop()
Idea
Essentially a DFS. The parameters of the helper function:
target: the remaining factors should multiply to target
start_num: the remaining factors should be equal to or larger than start_num
factors: the factors so far, stored in a list
res: result
Reference: https://discuss.leetcode.com/topic/21082/my-recursive-dfs-java-solution