C++_Backtracking_Accepted_0ms_76.66%


  • 0

    The main challenge is how to avoid duplicate elements. I used the start to control the loop.
    For example, n = 12, if we now have 3 and 4, and we push them into path vector, and them we need to consider when n = 4, but we should not reconsider i = 2 and 4 = 2*2 because we have consider it, so we need to start at i = 3!

    class Solution {
    public:
    vector<vector<int>> getFactors(int n) {
        vector<vector<int>> res;
        if(n <= 3) return res;
        vector<int> path;
        find(res, path, n, 2);
        return res;
    }
    
    void find(vector<vector<int>>& res, vector<int>& path, int n, int start){
        for(int i = start; i <= n/i; ++i){
            if(n % i == 0){
                path.push_back(i);
                path.push_back(n/i);
                res.push_back(path);
                path.pop_back();
                find(res, path, n/i, i);
                path.pop_back();
            }
        }
    }
    };

Log in to reply
 

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