[leetcode] 254. FactorCombinations解題レポート

タイトルリンク:https://leetcode.com/problems/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.
Examples:  input:  1 output: 

[]

input:  37
output: 

[]

input:  12
output:

[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]

input:  32
output:

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

考え方:DFS+backtracking.検索のたびに最小の係数からsqrt(n)表示までの数がnで除算できるかどうかは、可能であれば2つの選択肢があります.
1.nをこの因子で除算し、この因子を保持した後、次の層の探索を行う.
2.次のレベルの検索を行わず、現在の結果を保存します.
コードは次のとおりです.

class Solution {
public:
    void DFS(int k, int n, vector<int> tem)
    {
        for(int i = k; i <= sqrt(n); i++)
        {
            if(n%i==0)
            {
                tem.push_back(i);
                DFS(i, n/i, tem);
                tem.push_back(n/i);
                result.push_back(tem);
                tem.pop_back();
                tem.pop_back();
            }
        }
    }
    vector<vector<int>> getFactors(int n) {
        if(n <=1) return result;
        DFS(2, n, vector<int>(0));
        return result;
    }
private:
    vector<vector<int>> result;
};

参照先:https://leetcode.com/discuss/65106/share-clean-and-simple-0ms-c-solution-with-explanation