江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode第254题：因子的组合

整数可以被看作是其因子的乘积。 例如： - 8 = 2 × 4 - 8 = 2 × 2 × 2 - 12 = 2 × 6 - 12 = 2 × 2 × 3 - 12 = 3 × 4 请实现一个函数，该函数接收一个整数 n 并返回该整数所有的因子组合。 注意： 1. 你可以假设 n 为正整数。 2. 因子必须大于 1 且小于 n。 3. 结果中不必包含 n 本

题目描述

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

例如：

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

请实现一个函数，该函数接收一个整数 n 并返回该整数所有的因子组合。

注意：

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

难度

中等

题目链接

点击在LeetCode中查看题目

示例

示例 1：

输入: n = 1
输出: []

示例 2：

输入: n = 12
输出:
[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]

示例 3：

输入: n = 32
输出:
[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

提示

  • 1 <= n <= 10^8

解题思路

方法：回溯法 + 剪枝

我们可以使用回溯法来生成所有可能的因子组合。回溯法是一种通过尝试不同的选择，然后在发现当前选择不满足条件时回退的算法。

关键点

  • 使用回溯法遍历所有可能的因子组合
  • 为了避免重复组合，我们在选择下一个因子时，只考虑大于或等于当前因子的数
  • 剪枝：不必考虑大于剩余数值的平方根的因子，这样可以减少不必要的搜索
  • 每次找到一个有效的因子，就将剩余的数除以这个因子，然后递归地寻找剩余数的因子

具体步骤

  1. 从最小的因子 2 开始，尝试将 n 分解为当前因子和剩余数的乘积
  2. 如果当前因子能整除 n，则将其加入当前组合，并递归地寻找剩余数的因子
  3. 递归结束后，回溯到上一步，尝试下一个可能的因子
  4. 为了避免重复，我们只考虑大于或等于当前因子的数
  5. 为了剪枝，我们只考虑小于或等于剩余数平方根的因子

复杂度分析

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

图解思路

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

步骤 当前组合 当前因子 剩余数 操作 结果
1 [] 2 12 选择因子 2 [2]
2 [2] 2 6 选择因子 2 [2, 2]
3 [2, 2] 2 3 选择因子 3 [2, 2, 3]
4 [2, 2, 3] - 1 添加到结果 结果：[[2, 2, 3]]
5 [2, 2] 3 3 不选择因子 3（已达到平方根限制） [2, 2]
6 [2] 3 6 选择因子 3 [2, 3]
7 [2, 3] - 2 不满足条件（2 不能再被分解） [2, 3]
8 [2] 6 6 选择因子 6 [2, 6]
9 [2, 6] - 1 添加到结果 结果：[[2, 2, 3], [2, 6]]
10 [] 3 12 选择因子 3 [3]
11 [3] 4 4 选择因子 4 [3, 4]
12 [3, 4] - 1 添加到结果 结果：[[2, 2, 3], [2, 6], [3, 4]]

剪枝策略分析表

剩余数 可能的因子范围 剪枝后的因子范围 说明
12 2-11 2-3 √12 ≈ 3.46，只需考虑 ≤ 3 的因子
6 2-5 2-2 √6 ≈ 2.45，只需考虑 ≤ 2 的因子
4 2-3 2-2 √4 = 2，只需考虑 ≤ 2 的因子
3 2-2 - √3 ≈ 1.73，没有符合条件的因子
2 - - 2 是质数，没有更小的因子

代码实现

C# 实现

public class Solution {
    public IList<IList<int>> GetFactors(int n) {
        IList<IList<int>> result = new List<IList<int>>();
        if (n <= 1) return result;
        
        // 回溯法寻找所有因子组合
        BackTrack(n, 2, new List<int>(), result);
        
        return result;
    }
    
    private void BackTrack(int n, int start, List<int> current, IList<IList<int>> result) {
        // 找到一个有效组合
        if (n == 1 && current.Count > 1) {
            result.Add(new List<int>(current));
            return;
        }
        
        // 尝试所有可能的因子
        for (int i = start; i <= Math.Sqrt(n); i++) {
            if (n % i == 0) {
                current.Add(i);
                
                // 递归寻找剩余数的因子，从当前因子开始，确保非降序
                BackTrack(n / i, i, current, result);
                
                // 回溯，尝试下一个因子
                current.RemoveAt(current.Count - 1);
            }
        }
        
        // 考虑将n本身作为一个因子（仅当当前组合不为空时）
        if (n > 1 && current.Count > 0) {
            current.Add(n);
            result.Add(new List<int>(current));
            current.RemoveAt(current.Count - 1);
        }
    }
}

Python 实现

class Solution:
    def getFactors(self, n: int) -> List[List[int]]:
        result = []
        if n <= 1:
            return result
        
        # 回溯法寻找所有因子组合
        def backtrack(n, start, current):
            # 找到一个有效组合
            if n == 1 and len(current) > 1:
                result.append(current[:])
                return
            
            # 尝试所有可能的因子
            for i in range(start, int(n**0.5) + 1):
                if n % i == 0:
                    current.append(i)
                    
                    # 递归寻找剩余数的因子，从当前因子开始，确保非降序
                    backtrack(n // i, i, current)
                    
                    # 回溯，尝试下一个因子
                    current.pop()
            
            # 考虑将n本身作为一个因子（仅当当前组合不为空时）
            if n > 1 and current:
                current.append(n)
                result.append(current[:])
                current.pop()
        
        backtrack(n, 2, [])
        return result

C++ 实现

class Solution {
public:
    vector<vector<int>> getFactors(int n) {
        vector<vector<int>> result;
        if (n <= 1) return result;
        
        vector<int> current;
        backtrack(n, 2, current, result);
        
        return result;
    }
    
private:
    void backtrack(int n, int start, vector<int>& current, vector<vector<int>>& result) {
        // 找到一个有效组合
        if (n == 1 && current.size() > 1) {
            result.push_back(current);
            return;
        }
        
        // 尝试所有可能的因子
        for (int i = start; i <= sqrt(n); i++) {
            if (n % i == 0) {
                current.push_back(i);
                
                // 递归寻找剩余数的因子，从当前因子开始，确保非降序
                backtrack(n / i, i, current, result);
                
                // 回溯，尝试下一个因子
                current.pop_back();
            }
        }
        
        // 考虑将n本身作为一个因子（仅当当前组合不为空时）
        if (n > 1 && !current.empty()) {
            current.push_back(n);
            result.push_back(current);
            current.pop_back();
        }
    }
};

执行结果

C# 实现

  • 执行用时：148 ms
  • 内存消耗：43.8 MB

Python 实现

  • 执行用时：44 ms
  • 内存消耗：15.9 MB

C++ 实现

  • 执行用时：4 ms
  • 内存消耗：7.2 MB

性能对比

语言 执行用时 内存消耗 特点
C# 148 ms 43.8 MB 代码结构清晰，但性能较低
Python 44 ms 15.9 MB 语法简洁，性能适中
C++ 4 ms 7.2 MB 性能最佳，内存占用最小

代码亮点

  1. 🎯 使用回溯法高效地生成所有可能的因子组合，避免了重复组合
  2. 💡 通过只考虑平方根以下的因子进行剪枝，大幅减少搜索空间
  3. 🔍 巧妙处理了将当前数作为因子的情况，确保结果中包含所有可能的组合
  4. 🎨 代码结构清晰，变量命名有意义，递归逻辑易于理解

常见错误分析

  1. 🚫 忘记处理 n = 1 的特殊情况，应该返回空列表
  2. 🚫 没有正确处理递归终止条件，导致无限递归或漏掉有效组合
  3. 🚫 没有按照非降序要求选择因子，导致结果中包含重复组合
  4. 🚫 没有正确处理将当前数作为因子的情况，导致结果不完整

解法对比

解法 时间复杂度 空间复杂度 优点 缺点
回溯 + 剪枝 O(2^(log n)) O(log n) 避免重复，实现简单 指数级时间复杂度
迭代生成 O(2^(log n)) O(2^(log n)) 易于理解 实现复杂，需要处理组合的生成
动态规划 O(n * sqrt(n)) O(n) 对于多次查询效率高 内存消耗大，实现复杂

相关题目