LeetCode 254 Factor Combinations 因子组合全解：回溯法与迭代 DFS 双解法剖析（附 10 种语言实现）

LeetCode 254 Factor Combinations 因子组合全解：回溯法与迭代 DFS 双解法剖析（附 10 种语言实现）

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本篇文章基于本仓库 factor-combinations.md 的题解内容，系统讲解 LeetCode 254 "Factor Combinations"（因子组合）问题：如何找出整数n的所有因子组合（每个因子大于 1 且小于n，乘积等于n，且组合内因子按非递减顺序排列）。文章完整覆盖两种主流解法——递归回溯与迭代 DFS 的原理、算法流程、多语言实现与复杂度分析，并总结该题最容易踩的三个坑，帮助读者一次性吃透“去重 + 剪枝”的回溯套路。

前置知识（Prerequisites）

在动手实现之前，需要先掌握以下四个基础点：

• 回溯（Backtracking）：通过“做出选择 → 递归 → 撤销选择”的方式穷举所有可能性，是本题的核心算法范式；
• 因数分解（Factorization）：能够找出一个数的所有约数，并理解因子对（factor pairs）的概念；
• 递归（Recursion）：通过递归调用逐步构建解；
• 去重（Avoiding Duplicates）：通过在组合中保持因子的非递减顺序，防止生成重复结果。

仓库中其他与数论/因数相关的题解可作为延伸阅读：count-primes.md（素数计数）与 greatest-common-divisor-traversal.md（基于质因数分解的连通性遍历）。

问题本质

给定整数n，返回所有满足以下条件的组合：

• 组合中每个因子都大于1且小于n；
• 组合内所有因子的乘积恰好等于n；
• 组合内的因子按非递减顺序排列（保证唯一性）。

例如n = 12的因子组合包括[2, 6]、[2, 2, 3]、[3, 4]，而[1, 12]、[12]以及[6, 2]都是非法的（前者包含被禁止的1/n，后者顺序重复）。

解法一：回溯（Backtracking）

核心直觉

要找出n的所有唯一因子组合，我们使用回溯。每一步取出当前组合中的最后一个因子，尝试把它拆成两个更小的因子。只考虑大于等于前一个因子的数，就能避免生成[2, 6]与[6, 2]这类重复组合。

关键洞察是：对于一个乘积，我们只需要尝试到该乘积的平方根为止。若i能整除该乘积，则i与product/i都是因子，随后以product/i继续递归。

算法步骤

1. 用factors = [n]初始化，并准备一个空的结果列表ans；
2. 在回溯函数中：
   • 若factors的元素个数大于 1，说明当前组合合法，将它的副本加入结果；
   • 弹出最后一个因子，记为lastFactor；
   • 确定枚举起点：若factors为空则从2开始，否则从factors中剩余的最后一个因子开始；
   • 对i从起点遍历到sqrt(lastFactor)：
     • 若i能整除lastFactor，则把i与lastFactor / i压入factors，递归，再弹出二者完成回溯；
   • 返回前把lastFactor重新放回factors恢复现场；
3. 返回结果列表。

多语言实现

Python

class Solution: def _backtracking(self, factors: List[int], ans: List[List[int]]) -> None: # Got a solution. if len(factors) > 1: ans.append(factors.copy()) last_factor = factors.pop() i = 2 if not factors else factors[-1] while i <= last_factor // i: if last_factor % i == 0: # Add i and last_factor // i. factors.append(i) factors.append(last_factor // i) self._backtracking(factors, ans) # Remove the last 2 elements in factors to restore it after the recursion returns. factors.pop() factors.pop() i += 1 # Add last_factor back to factors to restore it. factors.append(last_factor) def getFactors(self, n: int) -> List[List[int]]: ans = [] self._backtracking([n], ans) return ans

Java

class Solution { private void backtracking(final LinkedList<Integer> factors, final List<List<Integer>> ans) { // Got a solution. if (factors.size() > 1) { ans.add(new ArrayList(factors)); } final int lastFactor = factors.removeLast(); for (int i = factors.isEmpty() ? 2 : factors.peekLast(); i <= lastFactor / i; ++i) { if (lastFactor % i == 0) { // Add i and lastFactor / i. factors.add(i); factors.add(lastFactor / i); backtracking(factors, ans); // Remove the last 2 elements in factors to restore it after the recursion returns. factors.removeLast(); factors.removeLast(); } } // Add lastFactor back to factors to restore it. factors.add(lastFactor); } public List<List<Integer>> getFactors(int n) { final List<List<Integer>> ans = new LinkedList<>(); backtracking(new LinkedList<>(Arrays.asList(n)), ans); return ans; } }

C++

class Solution { void backtracking(vector<int>& factors, vector<vector<int>>& ans) { // Got a solution, if (factors.size() > 1) { ans.push_back(factors); } const int lastFactor = factors.back(); factors.pop_back(); for (int i = factors.empty() ? 2 : factors.back(); i <= lastFactor / i; ++i) { if (lastFactor % i == 0) { // Add i and lastFactor / i. factors.push_back(i); factors.push_back(lastFactor / i); backtracking(factors, ans); // Remove the last 2 elements in factors to restore it after the recursion returns factors.pop_back(); factors.pop_back(); } } // Add lastFactor back to factors to restore it. factors.push_back(lastFactor); } public: vector<vector<int>> getFactors(int n) { vector<int> factors = {n}; vector<vector<int>> ans; backtracking(factors, ans); return ans; } };

JavaScript

class Solution { /** * @param {number[]} factors * @param {number[][]} ans */ _backtracking(factors, ans) { // Got a solution. if (factors.length > 1) { ans.push([...factors]); } const lastFactor = factors.pop(); for ( let i = factors.length === 0 ? 2 : factors[factors.length - 1]; i <= Math.floor(lastFactor / i); ++i ) { if (lastFactor % i === 0) { // Add i and lastFactor / i. factors.push(i); factors.push(Math.floor(lastFactor / i)); this._backtracking(factors, ans); // Remove the last 2 elements in factors to restore it after the recursion returns. factors.pop(); factors.pop(); } } // Add lastFactor back to factors to restore it. factors.push(lastFactor); } /** * @param {number} n * @return {number[][]} */ getFactors(n) { const ans = []; this._backtracking([n], ans); return ans; } }

C#

public class Solution { private void Backtracking(List<int> factors, List<IList<int>> ans) { // Got a solution. if (factors.Count > 1) { ans.Add(new List<int>(factors)); } int lastFactor = factors[factors.Count - 1]; factors.RemoveAt(factors.Count - 1); int start = factors.Count == 0 ? 2 : factors[factors.Count - 1]; for (int i = start; i <= lastFactor / i; i++) { if (lastFactor % i == 0) { // Add i and lastFactor / i. factors.Add(i); factors.Add(lastFactor / i); Backtracking(factors, ans); // Remove the last 2 elements in factors to restore it after the recursion returns. factors.RemoveAt(factors.Count - 1); factors.RemoveAt(factors.Count - 1); } } // Add lastFactor back to factors to restore it. factors.Add(lastFactor); } public IList<IList<int>> GetFactors(int n) { List<IList<int>> ans = new List<IList<int>>(); Backtracking(new List<int> { n }, ans); return ans; } }

Go

func getFactors(n int) [][]int { ans := [][]int{} var backtracking func(factors []int) backtracking = func(factors []int) { // Got a solution. if len(factors) > 1 { tmp := make([]int, len(factors)) copy(tmp, factors) ans = append(ans, tmp) } lastFactor := factors[len(factors)-1] factors = factors[:len(factors)-1] start := 2 if len(factors) > 0 { start = factors[len(factors)-1] } for i := start; i <= lastFactor/i; i++ { if lastFactor%i == 0 { // Add i and lastFactor / i. factors = append(factors, i) factors = append(factors, lastFactor/i) backtracking(factors) // Remove the last 2 elements in factors to restore it after the recursion returns. factors = factors[:len(factors)-2] } } // Add lastFactor back to factors to restore it. factors = append(factors, lastFactor) } backtracking([]int{n}) return ans }

Kotlin

class Solution { private fun backtracking(factors: MutableList<Int>, ans: MutableList<List<Int>>) { // Got a solution. if (factors.size > 1) { ans.add(factors.toList()) } val lastFactor = factors.removeAt(factors.size - 1) val start = if (factors.isEmpty()) 2 else factors[factors.size - 1] var i = start while (i <= lastFactor / i) { if (lastFactor % i == 0) { // Add i and lastFactor / i. factors.add(i) factors.add(lastFactor / i) backtracking(factors, ans) // Remove the last 2 elements in factors to restore it after the recursion returns. factors.removeAt(factors.size - 1) factors.removeAt(factors.size - 1) } i++ } // Add lastFactor back to factors to restore it. factors.add(lastFactor) } fun getFactors(n: Int): List<List<Int>> { val ans = mutableListOf<List<Int>>() backtracking(mutableListOf(n), ans) return ans } }

Swift

class Solution { func getFactors(_ n: Int) -> [[Int]] { var ans = [[Int]]() func backtracking(_ factors: inout [Int]) { // Got a solution. if factors.count > 1 { ans.append(factors) } let lastFactor = factors.removeLast() let start = factors.isEmpty ? 2 : factors[factors.count - 1] var i = start while i <= lastFactor / i { if lastFactor % i == 0 { // Add i and lastFactor / i. factors.append(i) factors.append(lastFactor / i) backtracking(&factors) // Remove the last 2 elements in factors to restore it after the recursion returns. factors.removeLast() factors.removeLast() } i += 1 } // Add lastFactor back to factors to restore it. factors.append(lastFactor) } var initial = [n] backtracking(&initial) return ans } }

Rust

impl Solution { pub fn get_factors(n: i32) -> Vec<Vec<i32>> { let mut ans = Vec::new(); fn backtracking(factors: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>) { if factors.len() > 1 { ans.push(factors.clone()); } let last_factor = factors.pop().unwrap(); let start = if factors.is_empty() { 2 } else { *factors.last().unwrap() }; let mut i = start; while i <= last_factor / i { if last_factor % i == 0 { factors.push(i); factors.push(last_factor / i); backtracking(factors, ans); factors.pop(); factors.pop(); } i += 1; } factors.push(last_factor); } let mut factors = vec![n]; backtracking(&mut factors, &mut ans); ans } }

复杂度分析

• 时间复杂度：$O(n^{1.5})$
• 空间复杂度：$O(\log n)$

其中 $n$ 为输入整数n。

空间复杂度为 $O(\log n)$ 的原因在于：该实现全程复用一个factors列表（就地修改、就地恢复），递归深度由连续拆分产生，约为 $\log n$ 量级。

解法二：迭代 DFS（显式栈）

核心直觉

迭代版本用显式栈代替系统递归。栈中的每个元素都存放一份“正在构建的因子列表”。每次弹出一个状态，取出其最后一个因子，尝试把它拆成两个更小的因子。

与回溯版的区别在于：迭代版为每个分支新建因子列表，而不是修改并恢复同一个列表。这样逻辑更简单、更不容易出错，但会占用更多内存。

算法步骤

1. 用栈初始化[n]，准备空的结果列表；
2. 当栈不为空时循环：
   • 弹出一个因子列表，取出最后一个元素作为lastFactor；
   • 确定枚举起点：若列表为空则从2开始，否则从列表中剩余的最后一个因子开始；
   • 对i从起点遍历到sqrt(lastFactor)：
     • 若i能整除lastFactor，则创建一个新列表：保留原剩余因子，再追加i与lastFactor / i；
     • 将新列表压入栈，同时加入结果；
3. 返回结果列表。

多语言实现

Java

class Solution { public List<List<Integer>> getFactors(int n) { final List<List<Integer>> ans = new LinkedList<>(); final Stack<LinkedList<Integer>> stack = new Stack<>(); stack.push(new LinkedList<>(new LinkedList<>(Arrays.asList(n)))); while (!stack.isEmpty()) { final LinkedList<Integer> factors = stack.pop(); final int lastFactor = factors.removeLast(); for (int i = factors.isEmpty() ? 2 : factors.peekLast(); i <= lastFactor / i; ++i) { if (lastFactor % i == 0) { // Add i and lastFactor / i. LinkedList<Integer> newFactors = new LinkedList<>(factors); newFactors.add(i); newFactors.add(lastFactor / i); stack.push(newFactors); ans.add(new LinkedList<>(newFactors)); } } } return ans; } }

C++

class Solution { public: vector<vector<int>> getFactors(int n) { vector<vector<int>> ans; stack<vector<int>> stack; stack.push({n}); while (!stack.empty()) { auto factors = stack.top(); stack.pop(); const int lastFactor = factors.back(); factors.pop_back(); for (int i = factors.empty() ? 2 : factors.back(); i <= lastFactor / i; ++i) { if (lastFactor % i == 0) { vector<int> newFactors = factors; newFactors.push_back(i); newFactors.push_back(lastFactor / i); stack.push(newFactors); ans.push_back(newFactors); } } } return ans; } };

JavaScript

class Solution { /** * @param {number} n * @return {number[][]} */ getFactors(n) { const ans = []; const stack = [[n]]; while (stack.length > 0) { const factors = stack.pop(); const lastFactor = factors.pop(); const start = factors.length === 0 ? 2 : factors[factors.length - 1]; for (let i = start; i <= Math.floor(lastFactor / i); i++) { if (lastFactor % i === 0) { const newFactors = [ ...factors, i, Math.floor(lastFactor / i), ]; stack.push(newFactors); ans.push(newFactors); } } } return ans; } }

C#

public class Solution { public IList<IList<int>> GetFactors(int n) { List<IList<int>> ans = new List<IList<int>>(); Stack<List<int>> stack = new Stack<List<int>>(); stack.Push(new List<int> { n }); while (stack.Count > 0) { List<int> factors = stack.Pop(); int lastFactor = factors[factors.Count - 1]; factors.RemoveAt(factors.Count - 1); int start = factors.Count == 0 ? 2 : factors[factors.Count - 1]; for (int i = start; i <= lastFactor / i; i++) { if (lastFactor % i == 0) { List<int> newFactors = new List<int>(factors); newFactors.Add(i); newFactors.Add(lastFactor / i); stack.Push(newFactors); ans.Add(new List<int>(newFactors)); } } } return ans; } }

Go

func getFactors(n int) [][]int { ans := [][]int{} stack := [][]int{{n}} for len(stack) > 0 { factors := stack[len(stack)-1] stack = stack[:len(stack)-1] lastFactor := factors[len(factors)-1] factors = factors[:len(factors)-1] start := 2 if len(factors) > 0 { start = factors[len(factors)-1] } for i := start; i <= lastFactor/i; i++ { if lastFactor%i == 0 { newFactors := make([]int, len(factors)) copy(newFactors, factors) newFactors = append(newFactors, i, lastFactor/i) stack = append(stack, newFactors) result := make([]int, len(newFactors)) copy(result, newFactors) ans = append(ans, result) } } } return ans }

Kotlin

class Solution { fun getFactors(n: Int): List<List<Int>> { val ans = mutableListOf<List<Int>>() val stack = ArrayDeque<MutableList<Int>>() stack.add(mutableListOf(n)) while (stack.isNotEmpty()) { val factors = stack.removeLast() val lastFactor = factors.removeAt(factors.size - 1) val start = if (factors.isEmpty()) 2 else factors[factors.size - 1] var i = start while (i <= lastFactor / i) { if (lastFactor % i == 0) { val newFactors = factors.toMutableList() newFactors.add(i) newFactors.add(lastFactor / i) stack.add(newFactors.toMutableList()) ans.add(newFactors.toList()) } i++ } } return ans } }

Swift

class Solution { func getFactors(_ n: Int) -> [[Int]] { var ans = [[Int]]() var stack = [[n]] while !stack.isEmpty { var factors = stack.removeLast() let lastFactor = factors.removeLast() let start = factors.isEmpty ? 2 : factors[factors.count - 1] var i = start while i <= lastFactor / i { if lastFactor % i == 0 { var newFactors = factors newFactors.append(i) newFactors.append(lastFactor / i) stack.append(newFactors) ans.append(newFactors) } i += 1 } } return ans } }

Rust

impl Solution { pub fn get_factors(n: i32) -> Vec<Vec<i32>> { let mut ans = Vec::new(); let mut stack: Vec<Vec<i32>> = vec![vec![n]]; while let Some(mut factors) = stack.pop() { let last_factor = factors.pop().unwrap(); let start = if factors.is_empty() { 2 } else { *factors.last().unwrap() }; let mut i = start; while i <= last_factor / i { if last_factor % i == 0 { let mut new_factors = factors.clone(); new_factors.push(i); new_factors.push(last_factor / i); stack.push(new_factors.clone()); ans.push(new_factors); } i += 1; } } ans } }

复杂度分析

• 时间复杂度：$O(n^{1.5})$
• 空间复杂度：$O(n \cdot \log n)$

其中 $n$ 为输入整数n。

空间复杂度显著高于回溯版：因为每个分支都会复制并持有独立的因子列表，栈中最多可能同时存在 $O(n \cdot \log n)$ 量级的状态。

两种解法对比

常见误区（Common Pitfalls）

1. 生成重复组合

最常见的错误是产出[2, 6]与[6, 2]这类互为排列的重复结果。解决办法：始终保证因子按非递减顺序加入组合——只考虑大于等于当前组合中前一个因子的候选值。这正是两种解法中“起点从2或列表末尾因子开始”的原因。

2. 把 1 或 n 本身当成因子

题目明确排除1和n本身作为合法因子。如果忘记这条约束，就会把[1, n]或[n]这类平凡分解混入答案。解决办法：因子候选一律从2开始枚举，并且在拆分时保证i不会走到n（平方根边界天然保证了这一点）。

3. 低效的因子搜索

若把因子搜索范围扩大到n而不是sqrt(n)，会产生大量无意义的迭代。原理：因子总是成对出现——若i整除n，则n/i也整除n。因此只需要检查到当前乘积的平方根，就能穷尽所有因子对。这也是两种解法时间复杂度的关键优化点。

总结

Factor Combinations 是回溯思想在数论问题上的经典应用。抓住三个要点即可举一反三：

1. 去重靠顺序：非递减枚举是避免重复组合的通用手段，同样适用于 combination-target-sum.md、subsets-ii.md 等组合类问题；
2. 剪枝靠平方根：因子成对的对称性让搜索量从 $O(n)$ 降到 $O(\sqrt{n})$；
3. 两种 DFS 实现互证：递归回溯（共享状态 + 现场恢复）与迭代栈（分支独立状态）在时间上等价，空间上各有取舍，可作为“递归改迭代”的标准演练。

完整题解原文见 factor-combinations.md，仓库中还有大量按语言分类的实现可供对照学习（如 python、java、javascript、cpp、go 等目录），可结合 README.md 中的题目索引快速定位。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode