Tuesday, December 29, 2015

254. Factor Combinations --------M ~!!!~~


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:

  1. You may assume that n is always positive.
  2. 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]
]

  A:
递归。 ---不是很必须用memorization, 因为每次的startFactor/minFactor不同。

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