254. 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:

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

[暴力解法]：

时间分析：

空间分析：

[优化后]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

［思维问题］：

知道是backtracing可是动不了笔：扩展就是n % i = 0添加因数就行了，退出条件就是把item添加到结果中

［英文数据结构或算法，为什么不用别的数据结构或算法］：

［一句话思路］：

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

递推表达式中的因数n要变成n/i
退出条件是n<= 1就肯定要用return退出，是否添加取决于item的size是否大于而不是等于1

［二刷］：

helper里面就是个参数，需要从start开始

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

退出条件是n<= 1就肯定要用return退出，是否添加取决于item的size是否大于而不是等于1

［复杂度］：Time complexity: O(乘以每个点是nlgn) Space complexity: O(递归树是lgn)

［算法思想：迭代/递归/分治/贪心］：

［关键模板化代码］：

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

[代码风格] ：

[是否头一次写此类driver funcion的代码] ：

[潜台词] ：

class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (n <= 0) return result;
        helper(2, new ArrayList<Integer>(), n, result);
        return result;
    }
    
    public void helper(int start, List<Integer> item, int n, List<List<Integer>> result) {
        //add the item to the result
        if (n <= 1) {
            if (item.size() > 1) 
                result.add(new ArrayList<Integer>(item));
            return;
        }
        
        //calculate the factors
        for (int i = start; i <= n; i++) {
            if (n % i == 0) {
                item.add(i);
                helper(i, item, n / i, result);
                item.remove(item.size() - 1);
            }
        }
    }
}

View Code