254. Factor Combinations
254. Factor Combinations
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].
def getFactors(self, n):
factorizations = []
def backtrack(candidate, prev_factor, reminder):
if len(candidate):
factorizations.append(candidate + [reminder])
for factor in range(prev_factor, int(reminder ** .5) + 1):
if reminder % factor == 0:
candidate.append(factor)
backtrack(candidate, factor, reminder // factor)
candidate.pop()
backtrack([], 2, n)
return factorizations