254. Factor Combinations

Posted on Edited on In

254. Factor Combinations

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: []

Constraints:

  • 1 <= n <= 10^7

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int n;
    vector<vector<int>> res;

    vector<vector<int>> getFactors(int n) {
        this->n = n;
        vector<int> cur;
        helper(n, cur, 2);
        return res;
    }

    void helper(int val, vector<int>& cur, int prev) {
        if (val == 1) {
            if (!cur.empty()) {
                res.push_back(cur);
            }
            return;
        }
        for (int i = prev; i <= min(val, n - 1); i++) {
            if (val % i == 0) {
                cur.push_back(i);
                helper(val / i, cur, i);
                cur.pop_back();
            }
        }
    }
};