9ms c++ solution, very straight-forward by checking if we are in recursion


  • 0

    The trick is to check if we are in recursion call, if yes, we need to add n itself to the result, so that upper level recursion call can use it.

    e.g. n = 12 and we starts with i = 2, recursively calculate getFactor(6) and because we are in recursion, we need to put "6" to the result returned by getFactor(6), which gives us: [[2, 3], [6]], and in the upper level getFactor(12), we add 2 to the front of the recursion results, which gives us final answer of: [[2, 2, 3], [2, 6]].

        vector<vector<int>> getFactors(int n, bool inRecursion) {
            vector<vector<int>> res;
            
            for (int i = 2; i * i <= n; ++ i) {
                if (n % i == 0) {
                    for (vector<int> &v : getFactors(n / i, true))
                        if (i <= v[0]) {
                            v.insert(v.begin(), i);
                            res.push_back(v);
                        }
                }
            }
            
            if (inRecursion) // if we are in recursion, need to add n itself in result to be used in upper level call
                res.push_back({n});
            
            return res;
        }
    
        vector<vector<int>> getFactors(int n) {
            return getFactors(n, false);
        }
    

Log in to reply
 

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