0254. 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:

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]
]

Analysis

In order to generate all the valid factors, we need to make sure target % factor == 0. However, there is a problem: how to deal with duplication:

We use a variable index to track the current factor, and if we choose the current factor, we should not update the index, because we can potentially reuse the same factor multiple times.

Note: since all the factors cannot be greater than sqrt(num), in the inner loop, we just need to loop from index to sqrt(n)

Code

class Solution {
public:
    vector<vector<int>> getFactors(int n) {
        vector<vector<int>> res;
        helper(n, 2, {}, res);
        return res;
    }
    void helper(int n, int start, vector<int> out, vector<vector<int>>& res) {
        if (n == 1) {
            if (out.size() > 1) res.push_back(out);
            return;
        }
        for (int i = start; i <= sqrt(n); ++i) {
            if (n % i != 0) continue;
            out.push_back(i);
            helper(n / i, i, out, res);
            out.pop_back();
        }
    }
};

---

Last update: April 1, 2022