博文中会简要介绍Leetcode P0254题目分析及解题思路。
“Factor Combinations”是一道中等难度的题目，主要思路是使用回溯法枚举出所有可能的因子组合。
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].
这道题的基本思路是利用回溯法枚举所有因子组合。该思路比较直接，由小到大依次枚举因数即可。除此之外，需要考虑对回溯法的枚举复杂度进行优化，即用当前剩余乘数n的平方根作为枚举的右边界。但是如果使用上述优化方法，需要提前将当前枚举到因数f时可以形成的组合计算出来，并存入list中，这样才能避免枚举不到组合内的最后一个因数。
以下是Java的题解代码实现。
class Solution {
public List<List<Integer>> getFactors(int n) {
this.dfs(n, 2, new ArrayList<>());
return this.combinations;
}
private List<List<Integer>> combinations = new ArrayList<>();
private void dfs(int n, int begin, List<Integer> comb) {
int rt = (int) Math.sqrt(n);
for (int f=begin; f<rt+1; ++f) {
if (n%f == 0) {
comb.add(f);
// Record one combination
comb.add(n/f);
this.combinations.add(new ArrayList<>(comb));
comb.remove(comb.size()-1);
// Explore the next factor
this.dfs(n/f, f, comb);
comb.remove(comb.size()-1);
}
}
}
}
以下是C++的题解代码实现。
class Solution {
public:
vector<vector<int>> getFactors(int n) {
vector<int> comb;
_Dfs(n, 2, comb);
return _combinations;
}
private:
vector<vector<int>> _combinations;
void _Dfs(int n, int begin, vector<int> &comb) {
for (int f=begin; f<=sqrt(n); ++f) {
if (n%f == 0) {
comb.push_back(f);
// Record one combination
comb.push_back(n/f);
_combinations.push_back(comb);
comb.pop_back();
_Dfs(n/f, f, comb);
comb.pop_back();
}
}
}
};