Problem description:

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:

1
2
Input: n = 1
Output: []

Example 2:

1
2
Input: n = 12
Output: [[2,6],[3,4],[2,2,3]]

Example 3:

1
2
Input: n = 37
Output: []

Example 4:

1
2
Input: n = 32
Output: [[2,16],[4,8],[2,2,8],[2,4,4],[2,2,2,4],[2,2,2,2,2]]

Solution:

Iterative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def getFactors(self, n: int) -> List[List[int]]:
        # factors start from 2, do an iterative function with last combination
        # every time we find a new factor, append the combination for next use
        # also add to result
        todo, res = [(n, 2, [])], []
        while todo:
            n, i, comb = todo.pop()
            while i*i <= n:
                if n % i == 0: # find a factor i
                    res.append(comb + [i, n//i])
                    todo.append((n//i, i, comb+[i]))
                i += 1
        return res

Recursive

1
2
3
4
5
6
7
8
9
10
class Solution:
    def getFactors(self, n: int) -> List[List[int]]:
        def factor(n, i, combi, res):
            while i * i <= n:
                if n % i == 0:
                    res += combi + [i, n//i],
                    factor(n//i, i, combi+[i], res)
                i += 1
            return res
        return factor(n, 2, [], [])

time complexity: $O()$
space complexity: $O()$
reference:
related problem: