0ms Standard Backtracking Solution in C++


  • 0
    H
    vector<vector<int>> getFactors(int n) {
       vector<vector<int>> ret;
       if(n == 1){
           return ret;
       }
       vector<int> facComb;
       backtracking(ret,facComb,n,2);
    }
    void backtracking(vector<vector<int>>& ret, vector<int>& facComb, int n, int factor){
        if(n == 1){
            ret.push_back(facComb);
            return;
        }
        int sqroot = sqrt(n);
        for(int j = factor; j <=sqroot;j++){
            if(n%j == 0){
                  vector<int> facCombCopy = facComb;
                  facCombCopy.push_back(min(j,n/j));
                  facCombCopy.push_back(max(j,n/j));
                  ret.push_back(facCombCopy);
                  vector<int> facCombCopy2 = facComb;
                  if(j<= n/j){
                         facCombCopy2.push_back(j);
                         backtracking(ret,facCombCopy2,n/j,j);
                  }else{
                      return;
                  }
            }
        }
    }

Log in to reply
 

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