# [leetcode] Factor Combinations

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. Each combination’s factors must be sorted ascending, for example: The factors of 2 and 6 is `[2, 6]`, not `[6, 2]`.
2. You may assume that n is always positive.
3. Factors should be greater than 1 and less than n.

Examples:
input: `1`
output:

```[]
```

input: `37`
output:

```[]
```

input: `12`
output:

```[
[2, 6],
[2, 2, 3],
[3, 4]
]
```

input: `32`
output:

```[
[2, 16],
[2, 2, 8],
[2, 2, 2, 4],
[2, 2, 2, 2, 2],
[2, 4, 4],
[4, 8]
]
```

DFS approach.

When writing DFS algorithm, be aware of symmetric, which is, we must ‘retrieve spot’ after we backtrack from child nodes.

For example,

```thisRes.push_back(i);
DFS(n / i, res, thisRes);
thisRes.pop_back(); // pop i```

and

```if(thisRes.size() > 0){ // single factor is not allowed due to problem specification.
thisRes.push_back(n);
res.push_back(thisRes);
thisRes.pop_back();
}```

```class Solution {
public:
vector<vector<int>> getFactors(int n) {
vector<vector<int> > res;
vector<int> thisRes;
DFS(n, res, thisRes);
return res;
}

void DFS(int n, vector<vector<int> >& res, vector<int>& thisRes){
int i;
i = thisRes.size() == 0? 2: thisRes.back();// i is greater than last element in thisRes. This is to avoid duplicate and make thisRes in ascending order.
for(; i <= sqrt(n); i++){
if(n % i == 0){
//i is a factor of n
thisRes.push_back(i);
DFS(n / i, res, thisRes);
thisRes.pop_back(); // pop i
}
}
if(thisRes.size() > 0){
thisRes.push_back(n);
res.push_back(thisRes);
thisRes.pop_back();
}
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.