[leetcode]254. Factor Combinations因式组合

发布时间：2020-12-14 04:48:18 所属栏目：大数据来源：网络整理

导读：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. Fact

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],8],4],2],4,[4,8]
]

题意：

给定正整数n，返回所有乘积等于n的不同组合(除了n = n)。为避免重复，所有乘数单调递增。

思路：

backtracking

代码：

 1 class Solution {
 2     public List<List<Integer>> getFactors(int n) {
 3         List<List<Integer>> res = new ArrayList<>();
 4         helper(res,new ArrayList<>(),n,2);
 5         return res;
 6     }
 7     
 8     public void helper(List<List<Integer>> res,List<Integer> list,int n,int start){
 9         if(n == 1){
10             if(list.size() > 1){
11                 res.add(new ArrayList<>(list));
12                 return;
13             }
14         }
15         for(int i = start; i< = n; i++){
16             if(n % i== 0){
17                 list.add(i);
18                 helper(res,list,n/i,i);
19                 list.remove(list.size()-1);
20             }
21         }
22     }
23 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!