Simple C++ Solution using DFS


  • 0
    Y
    class Solution {
    public:
        vector<vector<int>> getFactors(int n) {
            vector<vector<int>> ans;
            if(n <= 1)
                return ans;
            vector<int> factor_vec;
            dfs(n, 2, ans, factor_vec);
            return ans;
        }
    private:
        void dfs(int n, int size, vector<vector<int>> &ans, vector<int> &factor_vec){
            vector<int> tmp_ans(size);
            int sta_idx = size - 2, bnd = sqrt(n*1.0);
            for(int i = 0; i < sta_idx; ++ i)
                tmp_ans[i] = factor_vec[i];
            for(int i = 2; i <= bnd; ++ i){
                if(n%i == 0){
                    if(size - 3 >= 0){
                        if(tmp_ans[size - 3] > i)
                            continue;
                    }
                    tmp_ans[size - 2] = i;
                    tmp_ans[size - 1] = n/i;
                    ans.push_back(tmp_ans);
                    if(i == n/i)
                        break;
                    dfs(n/i, size + 1, ans, tmp_ans);
                }
            }
        }
    };

Log in to reply
 

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