Clean Straightforward C++ 3ms Solution With Explanation


  • 0
    L
    class Solution {
    private:
        void helper(int n, vector<vector<int>>& res, vector<int> curr, int num, int start) {
            curr.push_back(n);
            if (curr.size() >= num) {
                res.push_back(curr);
                return ;
            }
            curr.pop_back();
            
            for (int i = start; i <= n / i; i++) {
                if (n % i == 0) {
                    curr.push_back(i);
                    helper(n / i, res, curr, num, i);
                    curr.pop_back();
                }
            }
        }
    public:
        vector<vector<int>> getFactors(int n) {
            vector<vector<int>> res;
            vector<int> curr;
            int len = 1; // the number of basic factors
            int temp = n;
            for (int i = 2; i <= temp / i; i++) {
                if (temp % i == 0) {
                    temp /= i;
                    i--;
                    len++;
                }
            }
            
            // from 2 factors to len factors
            for (int num = 2; num <= len; num++) {
                helper(n, res, curr, num, 2);
            }
            return res;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.