254. Factor Combinations - cocoder39/coco39_LC GitHub Wiki
the way of avoiding duplication here is similar with 204. Count Primes
tips:
- Having checked 12 = 2 * 6, it is not necessary to check 12 = 6 * 2
- 12 can be 2 * 2 * 3 or 3 * 2 * 2, avoid it by
int i = cur.empty() ? 2 : cur.back(). In other words, makecursorted, thus avoiding duplication
t(n) = O(n ^ 1/2) + O(n ^ 1/2) * t(n/2) = O(n ^ 1/2) * O(n ^ 1/4) ... + 0(n ^ 1/2 ^ log n) = O(n) + 0(n ^ (1/2 log n)) = 0(n ^ (1/2 * log n))
class Solution {
public:
vector<vector<int>> getFactors(int n) {
vector<vector<int>> res;
vector<int> cur;
helper(res, cur, n);
return res;
}
private:
void helper(vector<vector<int>>& res, vector<int>& cur, int n) {
//having checked 2 * 6, not necessary to check 6 * 2
//2 * 3 * 3 is duplicate of 3 * 2 * 2
for (int i = cur.empty() ? 2 : cur.back() ; i <= n / i; i++) {
if (n % i == 0) {
cur.push_back(i);
cur.push_back(n / i);
res.push_back(cur);
cur.pop_back();
helper(res, cur, n / i);
cur.pop_back();
}
}
}
};