- Factor Combinations
https://leetcode.com/problems/factor-combinations/
我的回溯(220ms)：
class Solution {
void dfs(vector<vector<int>> & res, vector<int> &now, int n, int start) {
if(n == 1) {
res.push_back(now);
return;
}
for(int i = start; i <= n; i++) {
if(n % i == 0) {
now.push_back(i);
dfs(res, now, n/i, i);
now.pop_back();
}
}
}
public:
vector<vector<int>> getFactors(int n) {
vector<vector<int>> res;
vector<int> now;
dfs(res,now,n,2);
res.pop_back();
return res;
}
};
别人的回溯(3ms)：
class Solution {
public:
void getResult(vector<vector<int>> &result,vector<int> &row,int n){
int i=row.empty()?2:row.back();
for(;i<=n/i;++i){
if(n%i==0){
row.push_back(i);
row.push_back(n/i);
result.push_back(row);
row.pop_back();
getResult(result,row,n/i);
row.pop_back();
}
}
}
vector<vector<int>> getFactors(int n) {
vector<vector<int>> result;
vector<int>row;
getResult(result,row,n);
return result;
}
};
284.Peeking Iterator
https://leetcode.com/discuss/59415/simple-solution-line-method-without-extra-member-variables
用复制构造函数
用bool has_next和int next_val
