LeetCode第254题_因子的组合

LeetCode第254题：因子的组合

题目描述

整数可以被看作是其因子的乘积。
比方：

• 8 = 2 × 4
  
• 8 = 2 × 2 × 2
  
• 12 = 2 × 6
  
• 12 = 2 × 2 × 3
  
• 12 = 3 × 4
  

请实现一个函数，该函数接收一个整数 n 并返回该整数全部的因子组合。
注意：

• 你可以假设 n 为正整数。
  
• 因子必须大于 1 且小于 n。
  
• 结果中不必包含 n 本身。
  
• 结果中的每个组合中的因子必须是非降序的。
  
• 结果中不能包含重复的组合。
  

难度

中等
题目链接

点击在LeetCode中检察题目
示例

示例 1：

1. 输入: n = 1
2. 输出: []

复制代码

示例 2：

1. 输入: n = 12
2. 输出:
3. [
4.   [2, 6],
5.   [2, 2, 3],
6.   [3, 4]
7. ]

复制代码

示例 3：

1. 输入: n = 32
2. 输出:
3. [
4.   [2, 16],
5.   [2, 2, 8],
6.   [2, 2, 2, 4],
7.   [2, 2, 2, 2, 2],
8.   [2, 4, 4],
9.   [4, 8]
10. ]

复制代码

提示

• 1 <= n <= 10^8
  

解题思路

方法：回溯法 + 剪枝

我们可以使用回溯法来生成全部大概的因子组合。回溯法是一种通过实验不同的选择，然后在发现当前选择不满意条件时回退的算法。
关键点

• 使用回溯法遍历全部大概的因子组合
  
• 为了制止重复组合，我们在选择下一个因子时，只思量大于或即是当前因子的数
  
• 剪枝：不必思量大于剩余数值的平方根的因子，如许可以淘汰不须要的搜索
  
• 每次找到一个有用的因子，就将剩余的数除以这个因子，然后递归地寻找剩余数的因子
  

具体步骤

• 从最小的因子 2 开始，实验将 n 分解为当前因子和剩余数的乘积
  
• 假如当前因子能整除 n，则将其加入当前组合，并递归地寻找剩余数的因子
  
• 递归结束后，回溯到上一步，实验下一个大概的因子
  
• 为了制止重复，我们只思量大于或即是当前因子的数
  
• 为了剪枝，我们只思量小于或即是剩余数平方根的因子
  

复杂度分析

• 时间复杂度：O(2^(log n))，其中 log n 是 n 的因子数量的上限。对于每个大概的因子，我们都有选择或不选择两种大概，总共有 log n 个大概的因子。
  
• 空间复杂度：O(log n)，递归栈的深度最多为 log n。
  

图解思路

回溯过程示例表（n = 12）

步骤当前组合当前因子剩余数操作结果1[]212选择因子 2[2]2[2]26选择因子 2[2, 2]3[2, 2]23选择因子 3[2, 2, 3]4[2, 2, 3]-1添加到结果结果：[[2, 2, 3]]5[2, 2]33不选择因子 3（已达到平方根限制）[2, 2]6[2]36选择因子 3[2, 3]7[2, 3]-2不满意条件（2 不能再被分解）[2, 3]8[2]66选择因子 6[2, 6]9[2, 6]-1添加到结果结果：[[2, 2, 3], [2, 6]]10[]312选择因子 3[3]11[3]44选择因子 4[3, 4]12[3, 4]-1添加到结果结果：[[2, 2, 3], [2, 6], [3, 4]] 剪枝计谋分析表

剩余数大概的因子范围剪枝后的因子范围说明122-112-3√12 ≈ 3.46，只需思量 ≤ 3 的因子62-52-2√6 ≈ 2.45，只需思量 ≤ 2 的因子42-32-2√4 = 2，只需思量 ≤ 2 的因子32-2-√3 ≈ 1.73，没有符合条件的因子2--2 是质数，没有更小的因子 代码实现

C# 实现

1. public class Solution {
2.     public IList<IList<int>> GetFactors(int n) {
3.         IList<IList<int>> result = new List<IList<int>>();
4.         if (n <= 1) return result;
5.         
6.         // 回溯法寻找所有因子组合
7.         BackTrack(n, 2, new List<int>(), result);
8.         
9.         return result;
10.     }
11.    
12.     private void BackTrack(int n, int start, List<int> current, IList<IList<int>> result) {
13.         // 找到一个有效组合
14.         if (n == 1 && current.Count > 1) {
15.             result.Add(new List<int>(current));
16.             return;
17.         }
18.         
19.         // 尝试所有可能的因子
20.         for (int i = start; i <= Math.Sqrt(n); i++) {
21.             if (n % i == 0) {
22.                 current.Add(i);
23.                
24.                 // 递归寻找剩余数的因子，从当前因子开始，确保非降序
25.                 BackTrack(n / i, i, current, result);
26.                
27.                 // 回溯，尝试下一个因子
28.                 current.RemoveAt(current.Count - 1);
29.             }
30.         }
31.         
32.         // 考虑将n本身作为一个因子（仅当当前组合不为空时）
33.         if (n > 1 && current.Count > 0) {
34.             current.Add(n);
35.             result.Add(new List<int>(current));
36.             current.RemoveAt(current.Count - 1);
37.         }
38.     }
39. }

复制代码

Python 实现

1. class Solution:
2.     def getFactors(self, n: int) -> List[List[int]]:
3.         result = []
4.         if n <= 1:
5.             return result
6.         
7.         # 回溯法寻找所有因子组合
8.         def backtrack(n, start, current):
9.             # 找到一个有效组合
10.             if n == 1 and len(current) > 1:
11.                 result.append(current[:])
12.                 return
13.             
14.             # 尝试所有可能的因子
15.             for i in range(start, int(n**0.5) + 1):
16.                 if n % i == 0:
17.                     current.append(i)
18.                     
19.                     # 递归寻找剩余数的因子，从当前因子开始，确保非降序
20.                     backtrack(n // i, i, current)
21.                     
22.                     # 回溯，尝试下一个因子
23.                     current.pop()
24.             
25.             # 考虑将n本身作为一个因子（仅当当前组合不为空时）
26.             if n > 1 and current:
27.                 current.append(n)
28.                 result.append(current[:])
29.                 current.pop()
30.         
31.         backtrack(n, 2, [])
32.         return result

复制代码

C++ 实现

1. class Solution {
2. public:
3.     vector<vector<int>> getFactors(int n) {
4.         vector<vector<int>> result;
5.         if (n <= 1) return result;
6.         
7.         vector<int> current;
8.         backtrack(n, 2, current, result);
9.         
10.         return result;
11.     }
12.    
13. private:
14.     void backtrack(int n, int start, vector<int>& current, vector<vector<int>>& result) {
15.         // 找到一个有效组合
16.         if (n == 1 && current.size() > 1) {
17.             result.push_back(current);
18.             return;
19.         }
20.         
21.         // 尝试所有可能的因子
22.         for (int i = start; i <= sqrt(n); i++) {
23.             if (n % i == 0) {
24.                 current.push_back(i);
25.                
26.                 // 递归寻找剩余数的因子，从当前因子开始，确保非降序
27.                 backtrack(n / i, i, current, result);
28.                
29.                 // 回溯，尝试下一个因子
30.                 current.pop_back();
31.             }
32.         }
33.         
34.         // 考虑将n本身作为一个因子（仅当当前组合不为空时）
35.         if (n > 1 && !current.empty()) {
36.             current.push_back(n);
37.             result.push_back(current);
38.             current.pop_back();
39.         }
40.     }
41. };

复制代码

执行结果

C# 实现

• 执行用时：148 ms
  
• 内存斲丧：43.8 MB
  

Python 实现

• 执行用时：44 ms
  
• 内存斲丧：15.9 MB
  

C++ 实现

• 执行用时：4 ms
  
• 内存斲丧：7.2 MB
  

性能对比

语言执行用时内存斲丧特点C#148 ms43.8 MB代码结构清晰，但性能较低Python44 ms15.9 MB语法简便，性能适中C++4 ms7.2 MB性能最佳，内存占用最小 代码亮点