LeetCode/C++/factor-combinations.cpp at master · pranerd/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// Time:  O(nlogn) = logn * n^(1/2) * n^(1/4) * ... * 1
// Space: O(logn)

// DFS solution.
class Solution {
    public:
        vector<vector<int>> getFactors(int n) {
            vector<vector<int>> result;
            vector<int> factors;
            getResult(n, &result, &factors);
            return result;
        }

        void getResult(const int n, vector<vector<int>> *result, vector<int> *factors) {
            for (int i = factors->empty() ? 2 : factors->back(); i <= n / i; ++i) {
                if (n % i == 0) {
                    factors->emplace_back(i);
                    factors->emplace_back(n / i);
                    result->emplace_back(*factors);
                    factors->pop_back();
                    getResult(n / i, result, factors);
                    factors->pop_back();
                }
            }
        }
    };