Swift 实现 LeetCode 254：因子组合问题的递归解法全解析

摘要

这篇文章我们来聊聊 LeetCode 第 254 题 ——「因子的组合」。看起来像是一个数学题，其实核心是递归和回溯的思路，非常适合锻炼你的算法基础和思维拆解能力。我们将用 Swift 实现完整解法，并结合实际场景聊聊它的应用，比如权限拆分、任务分解等。

描述

题目：Factor Combinations（因子的组合）

给你一个整数 n，请你返回所有该整数的因子组合（不包括 1 和它本身）。

每种组合中的因子按升序排列，所有组合不能重复。

示例：

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

题解答案（Swift 实现）

我们使用回溯 + 剪枝的方法来解决这个问题。遍历从 2 到 sqrt(n) 的所有数，检查是否为因子，然后递归进行组合。

class Solution {func getFactors(_ n: Int) -> [[Int]] {var res = [[Int]]()var path = [Int]()func backtrack(_ start: Int, _ target: Int) {if target == 1 {if path.count > 1 {res.append(path)}return}for i in start...target {if i * i > target { break }if target % i == 0 {path.append(i)backtrack(i, target / i)path.removeLast()}}// 把 target 本身也算一个因子（如果不是第一次递归）if target >= start {path.append(target)if path.count > 1 {res.append(path)}path.removeLast()}}backtrack(2, n)return res}
}

题解代码分析

核心思路：

1. 我们从 2 开始遍历，避免使用 1。
2. 每当遇到一个因子 i，我们将 i 加入当前路径，并继续尝试 n/i。
3. 如果最后乘积为原始 n，就加入结果。
4. 为避免重复组合，下一轮递归的起始因子要从当前因子开始。

举个例子：

对于 n = 12：

• 2 是因子，递归进入 getFactors(6)
  • 2 是因子，递归进入 getFactors(3)
    • 3 是因子 → [2, 2, 3]
  • 3 是因子 → [2, 6]
• 3 是因子 → [3, 4]

示例测试及结果

你可以直接在 Xcode 的 Playground 里跑下面这段代码测试：

let s = Solution()
let result = s.getFactors(12)
print(result)
// 输出：[[2, 2, 3], [2, 6], [3, 4]]

这个例子很直观地展示了 12 被分解成哪些乘积形式。

时间复杂度分析

• 最坏情况下，我们要递归所有可能的因子组合，所以时间复杂度是接近指数级。
• 但由于剪枝策略（只遍历到 √n），加上组合结果数目不会太多，因此实际运行非常快。

空间复杂度分析

• 路径栈空间最多为 log(n)，因为每层递归最多压入一个因子。
• 所以空间复杂度是 O(log n + R)，R 是最终结果的组合数量。

现实应用场景结合

你可能会问，这种“分解因子”有什么用？

其实在很多实际场景里，类似的“因子组合”问题都广泛存在：

• 权限系统设计：你有一个大的权限值，希望拆成多个基础权限组合。
• 任务拆分：一个大任务 T，需要拆成多个能组合成 T 的子任务。
• 理财分配：将一定资金拆成若干个乘积组合，用于不同类型的产品配置。

这些问题的共同点都是：在不重复的前提下，把一个整体拆成有意义的组合。

总结

LeetCode 254 这个题虽然看起来偏数学，但它的解法其实是经典的回溯算法题型。只要理解了“从当前起点向后找因子、递归拆解”的逻辑，就能轻松应对类似的组合问题。

如果你正在学 Swift 的算法题，推荐把这个问题记住，因为它在多个场景下都能用得上。下次遇到任务组合、拆解、分配一类的问题时，这道题的思路可能就能帮上忙了。