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:
- You may assume that n is always positive.
- Factors should be greater than 1 and less than n.
Example 1:
Input: 1
Output: []
Example 2:
Input: 37
Output:[]
Example 3:
Input: 12
Output:
[
[2, 6],
[2, 2, 3],
[3, 4]
]
Example 4:
Input: 32
Output:
[
[2, 16],
[2, 2, 8],
[2, 2, 2, 4],
[2, 2, 2, 2, 2],
[2, 4, 4],
[4, 8]
]
递归。 ---不是很必须用memorization, 因为每次的startFactor/minFactor不同。
Mistakes:
1: 为了代码缩减,因此直接在helper()中的for loop中 i <= n
因此,需要删掉最后一个 32 的<32)>. 因此需要在主函数中删掉最后一个。
class Solution { public: vector<vector<int>> getFactors(int n) { auto res = helper(2, n); if (not res.empty()) res.pop_back(); // pop out {n}, return res; } private: vector<vector<int>> helper(int startFactor, int n) { vector<vector<int>> res; for (int i = startFactor; i <= n; i++) { if (n % i == 0) { if (i == n) { res.push_back(vector<int>{n}); // this would need to be deleted } else { auto lessAll = helper(i, n / i); for (auto& line : lessAll) { line.insert(line.begin(), i); res.push_back(line); } } } } return res; } };
Mistakes:
1: 为了代码缩减,因此直接在helper()中的for loop中 i <= n
因此,需要删掉最后一个 32 的<32)>. 因此需要在主函数中删掉最后一个。
No comments:
Post a Comment