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:
Input: n = 1 Output: []
Example 2:
Input: n = 12 Output: [[2,6],[3,4],[2,2,3]]
Example 3:
Input: n = 37 Output: []
Constraints:
1 <= n <= 107
Companies: LinkedIn, TikTok, Uber
Related Topics:
Array, Backtracking
Similar Questions:
// OJ: https://leetcode.com/problems/factor-combinations
// Author: github.com/lzl124631x
// Time: O(?)
// Space: O(?)
class Solution {
public:
vector<vector<int>> getFactors(int n) {
vector<vector<int>> ans;
vector<int> tmp;
function<void(int, int)> dfs = [&](int n, int d) {
for (int i = d; i * i <= n; ++i) {
if (n % i) continue;
tmp.push_back(i);
dfs(n / i, i);
tmp.push_back(n / i);
ans.push_back(tmp);
tmp.pop_back();
tmp.pop_back();
}
};
dfs(n, 2);
return ans;
}
};