README.md

254. Factor Combinations (Medium)

Numbers can be regarded as the product of their factors.

• For example, 8 = 2 x 2 x 2 = 2 x 4.

Given an integer n, return all possible combinations of its factors. You may return the answer in any order.

Note that the factors should be in the range [2, n - 1].

 

Example 1:

Input: n = 1
Output: []

Example 2:

Input: n = 12
Output: [[2,6],[3,4],[2,2,3]]

Example 3:

Input: n = 37
Output: []

 

Constraints:

• 1 <= n <= 107

Companies: LinkedIn, TikTok, Uber

Related Topics:
Array, Backtracking

Similar Questions:

• Combination Sum (Medium)

Solution 1. Backtracking

// OJ: https://leetcode.com/problems/factor-combinations
// Author: github.com/lzl124631x
// Time: O(?)
// Space: O(?)
class Solution {
public:
    vector<vector<int>> getFactors(int n) {
        vector<vector<int>> ans;
        vector<int> tmp;
        function<void(int, int)> dfs = [&](int n, int d) {
            for (int i = d; i * i <= n; ++i) {
                if (n % i) continue;
                tmp.push_back(i);
                dfs(n / i, i);
                tmp.push_back(n / i);
                ans.push_back(tmp);
                tmp.pop_back();
                tmp.pop_back();
            }
        };
        dfs(n, 2);
        return ans;
    }
};