254. Factor Combinations

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:

1. You may assume that  n  is always positive.
2. 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]
]
``````

``````class Solution {
public:
vector<vector<int>> getFactors(int n) {
vector<vector<int>> res;
helper(n, 2, {}, res);
return res;
}
void helper(int n, int start, vector<int> out, vector<vector<int>>& res) {
if (n == 1) {
if (out.size() > 1) res.push_back(out);
return;
}
for (int i = start; i <= n; ++i) {
if (n % i != 0) continue;
out.push_back(i);
helper(n / i, i, out, res);
out.pop_back();
}
}
};
``````

``````class Solution {
public:
vector<vector<int>> getFactors(int n) {
vector<vector<int>> res;
helper(n, 2, {}, res);
return res;
}
void helper(int n, int start, vector<int> out, vector<vector<int>> &res) {
for (int i = start; i <= sqrt(n); ++i) {
if (n % i != 0) continue;
vector<int> new_out = out;
new_out.push_back(i);
helper(n / i, i, new_out, res);
new_out.push_back(n / i);
res.push_back(new_out);
}
}
};
``````

``````n = 12
2 2 3
2 6
3 4

n = 32
2 2 2 2 2
2 2 2 4
2 2 8
2 4 4
2 16
4 8
``````

``````class Solution {
public:
vector<vector<int>> getFactors(int n) {
vector<vector<int>> res;
for (int i = 2; i * i <= n; ++i) {
if (n % i != 0) continue;
vector<vector<int>> v = getFactors(n / i);
vector<int> out{i, n / i};
res.push_back(out);
for (auto a : v) {
if (i <= a[0]) {
a.insert(a.begin(), i);
res.push_back(a);
}
}
}
return res;
}
};
``````

``````n = 12
2 6
2 2 3
3 4

n = 32
2 16
2 2 8
2 2 2 4
2 2 2 2 2
2 4 4
4 8
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/254

Combination Sum III

Combination Sum II

Combination Sum

https://leetcode.com/problems/factor-combinations/

https://leetcode.com/problems/factor-combinations/discuss/68039/A-simple-java-solution

https://leetcode.com/problems/factor-combinations/discuss/68040/My-Recursive-DFS-Java-Solution

https://leetcode.com/problems/factor-combinations/discuss/68132/Share-simple-C%2B%2B-DFS-accepted-solution

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation