Factor Combinations

Numbers can be regarded as product of its factors. For example,

8 = 2 x 2 x 2; = 2 x 4.

Write a function that takes an integer n and return all possible combinations of its factors.

Note:

Each combination's factors must be sorted ascending, for example: The factors of 2 and 6 is [2, 6], not [6, 2].
You may assume that n is always positive.
Factors should be greater than 1 and less than n.

input: 32 output:

[ [2, 16], [2, 2, 8], [2, 2, 2, 4], [2, 2, 2, 2, 2], [2, 4, 4], [4, 8] ]

用DFS做。

• 需要注意的情况有在什么情况下，不能把整个元素作为因子塞进去。

• DFS，可以返回后把值塞进去，也可以在最深的递归里把值塞进去。

  class Solution {
  public:
    vector<vector<int>> getFactors(int n) {
        if(n<=2)return vector<vector<int>>();
  
        return getF(n,2,true);
    }
  
    vector<vector<int>> getF(int n,int start,bool isStart=false)
    {
        if(n<start)return vector<vector<int>>();
        if(n==start)return vector<vector<int>>(1,vector<int>(1,start));
  
        vector<vector<int>> ret;
  
        if(!isStart)
        ret.push_back(vector<int>(1,n));
  
        for(int i=start;i<=n;i++)
        {
            if(n%i==0)
            {
                vector<vector<int>> tmp=getF(n/i,i);
  
                for(int j=0;j<tmp.size();j++)
                {
                    tmp[j].insert(tmp[j].begin(),i);
                    ret.push_back(tmp[j]);
                }
            }
        }
  
        return ret;
    }
  };