## Factor Combinations

• Time:O(n\log n)
• Space:O(\log n)

## C++

``````class Solution {
public:
vector<vector<int>> getFactors(int n) {
vector<vector<int>> ans;
dfs(n, 2, {}, ans);  // the smallest factor is 2
return ans;
}

private:
void dfs(int n, int s, vector<int>&& path, vector<vector<int>>& ans) {
if (n <= 1) {
if (path.size() > 1)
ans.push_back(path);
return;
}

for (int i = s; i <= n; ++i)
if (n % i == 0) {
path.push_back(i);
dfs(n / i, i, move(path), ans);
path.pop_back();
}
}
};
``````

## JAVA

``````class Solution {
public List<List<Integer>> getFactors(int n) {
List<List<Integer>> ans = new ArrayList<>();
dfs(n, 2, new ArrayList<>(), ans);
return ans;
}

private void dfs(int n, int s, List<Integer> path, List<List<Integer>> ans) {
if (n == 1) {
if (path.size() > 1)
return;
}

for (int i = s; i <= n; ++i)
if (n % i == 0) {
dfs(n / i, i, path, ans);
path.remove(path.size() - 1);
}
}
}
``````

## Python

``````class Solution:
def getFactors(self, n: int) -> List[List[int]]:
ans = []

def dfs(n: int, s: int, path: List[int]) -> None:
if n <= 1:
if len(path) > 1:
ans.append(path.copy())
return

for i in range(s, n + 1):
if n % i == 0:
path.append(i)
dfs(n // i, i, path)
path.pop()

dfs(n, 2, [])  # the smallest factor is 2
return ans
``````