# leetcode\_254

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:

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

## Solutions

1. **dfs**
2. Avoid duplicates by keeping factor sequences in ascending order.

```cpp
class Solution {
public:
    int maxn;
    vector<int> path;
    vector<vector<int>> res;
    void dfs(int n, int st) {
        if (n == 1) {
            if (path.size() > 1)
                res.push_back(path);
        }
        else {
            for (int fac = st; fac <= n; fac++) {
                if ((n % fac) != 0) continue;
                path.push_back(fac);
                dfs(n / fac, fac);
                path.pop_back();
            }
        }
    }
    vector<vector<int>> getFactors(int n) {
        maxn = n;
        dfs(n, 2);
        return res;
    }
};
```