### 题目

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. 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]
]


### 自底向上的动态规划

32 = 2 * 16
32 = 4 * 8
----------------
32 = 8 * 4      // 下半区，重复
32 = 16 * 2     // 下半区，重复


#### 代码

public class Solution {
private Map<Integer,Set<List<Integer>>> memo = new HashMap<>();
public List<List<Integer>> getFactors(int n) {
Set<List<Integer>> result = memo.get(n);
if (result != null) {
ArrayList<List<Integer>> resultList = new ArrayList<>();
return resultList;
}
result = new HashSet<>();
for (int i = 2; i <= (int)Math.sqrt(n); i++) { // 这里开方，省去很多重复操作
if ((n % i) == 0) {
int quotien = n / i;
Integer[] nums = new Integer[]{i,quotien};
Arrays.sort(nums);
List<List<Integer>> sublist = getFactors(quotien);
for (List<Integer> factors : sublist) {
List<Integer> localFactors = new ArrayList<>(factors);
Collections.sort(localFactors);
}
}
}
memo.put(n,result);
ArrayList<List<Integer>> resultList = new ArrayList<>();
return resultList;
}
}


### 回溯算法

#### 代码

public class Solution {
public List<List<Integer>> getFactors(int n) {
List<List<Integer>> result = new ArrayList<>();
backtracking(n,2,new ArrayList<Integer>(),result);
return result;
}
public void backtracking(int n, int start, List<Integer> path, List<List<Integer>> result) {
if (n < 2) {
if (!path.isEmpty()) { result.add(new ArrayList<Integer>(path)); } return;
}
for (int i = start; i <= (int)Math.sqrt(n); i++) { // start 和 sqrt 是去重的关键
if ((n % i) == 0) {
int quotien = n / i;
backtracking(quotien,i,path,result);