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);

            }

        }

    }

}

巴特西

254. Factor Combinations 返回所有因数组合

最新文章

热门文章