# 0254. Factor Combinations

https://leetcode.com/problems/factor-combinations

## Description

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:** []
```

**Example 4:**

```
**Input:** n = 32
**Output:** [[2,16],[4,8],[2,2,8],[2,4,4],[2,2,2,4],[2,2,2,2,2]]
```

**Constraints:**

* `1 <= n <= 107`

## ac

```java
// KEY: circumvent repeat, number always <= next one
class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> note = new ArrayList<Integer>();

        backtrack(res, note, n, 2);

        return res;
    }

    private void backtrack(List<List<Integer>> res, List<Integer> note, int n, int s) {
        // exit
        if (n <= 1) {
            if (note.size() > 1) {
                res.add(new ArrayList<Integer>(note));
            }
            return;
        }

        //  handle
        for (int i = s; i <= n; i++) {
            if (n % i == 0) {
                note.add(i);
                backtrack(res, note, n / i, i);
                note.remove(note.size()-1);
            }
        }
    }
}
```

## ac2:

key: `i = start; i <= n/i` ensure acending list

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

    private void helper(int n, int start, List<Integer> note, List<List<Integer>> res) {
        // exit
        if (note.size() > 0) {
            List<Integer> tmp = new ArrayList<Integer>(note);
            tmp.add(n);
            res.add(tmp);
        }

        for (int i = start; i <= n/i; i++) { // i <= n/i, list should be ascending
            if (n % i != 0) continue;
            note.add(i);
            helper(n / i, i, note, res);
            note.remove(note.size()-1);
        }
    }
}
```
