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.

递归

复杂度

O(2^N) 时间 O(N) 空间

思路

递归，为了防止2,2,3和2,3,2这种重复，参数里需要一个start
递归函数接口定义：

helper函数找n的所有因式分解，每个因式分解最小的因子从start开始，后面的因子们升序排列，把所有这样的因式分解放到result里

void helper(int n,    //对谁进行因式分解            int start,     //最小的因子有多大            List list,    //分解到n之前的因子们            List> result)    //结果

注意

输入的数不算做自己的因子
最开始的循环for(int i = start; i public class Solution {
public List> getFactors(int n) {
List> result = new ArrayList();
List list = new ArrayList();
helper(n, 2, list, result);
return result;
}
public void helper(int n, int start, List list, List> result) {
if (n == 1) {
if (list.size() > 1) { //the original input is not counted in
result.add(new ArrayList(list));
}
return;
}
for (int i = start; i

关键字：leetcode, list, int, result

版权声明

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击 举报 进行投诉反馈！