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:
- Each combination's factors must be sorted ascending, for example: The factors of 2 and 6 is
[2, 6]
, not[6, 2]
. - You may assume that n is always positive.
- Factors should be greater than 1 and less than n.
Examples:
input:
output:
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] ]
用dfs方法,
public class Solution { public List<List<Integer>> getFactors(int n) { List<List<Integer>> res = new ArrayList<List<Integer>>(); if (n <= 2) { return res; } List<Integer> tem = new ArrayList<Integer>(); helper(res, tem,n,2); return res; } public void helper(List<List<Integer>> res, List<Integer> tem, int m,int div) { if (m <= 1) { if (tem.size() > 1) { res.add(new ArrayList<Integer>(tem)); } return; } for (int i = div; i <= m; i++) { if (m % i == 0) { tem.add(i); helper(res, tem,m / i, i); tem.remove(tem.size() - 1); } } } }
没有评论:
发表评论