254. Factor Combinations

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

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. Example 1:

Input: 1
Output: []

Example 2:

Input: 37
Output:[]

Example 3:

Input: 12
Output:
[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]

Example 4:

Input: 32
Output:
[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

Code

class Solution {
    private void helper(List<List<Integer>> res, List<Integer> temp, int n, int start) {
        if (n == 1){
            if (temp.size() > 1) {
                res.add(new ArrayList<>(temp));
                return;
            }
        }

        for (int i = start; i <= n; i++){
            if(n % i == 0) {
                temp.add(i);
                helper(res, temp, n / i, i);
                temp.remove(temp.size() - 1);
            }
        }
    }

    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> res = new ArrayList<>();
        helper(res, new ArrayList<>(), n, 2);
        return res;
    }
}

class Solution:
    def helper(self, res: List[List[int]], temp: List[int], n: int, start: int):
        if n == 1:
            if len(temp) > 1:
                res.append(temp[:])
                return

        for i in range(start, n + 1, 1):
            if n % i == 0:
                temp.append(i)
                self.helper(res, temp, n // i, i)
                del temp[-1]

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