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继续递归。算法步骤用factors [n]初始化并准备一个空的结果列表ans在回溯函数中若factors的元素个数大于 1说明当前组合合法将它的副本加入结果弹出最后一个因子记为lastFactor确定枚举起点若factors为空则从2开始否则从factors中剩余的最后一个因子开始对i从起点遍历到sqrt(lastFactor)若i能整除lastFactor则把i与lastFactor / i压入factors递归再弹出二者完成回溯返回前把lastFactor重新放回factors恢复现场返回结果列表。多语言实现Pythonclass 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 ansJavaclass Solution { private void backtracking(final LinkedListInteger factors, final ListListInteger 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 ListListInteger getFactors(int n) { final ListListInteger ans new LinkedList(); backtracking(new LinkedList(Arrays.asList(n)), ans); return ans; } }Cclass Solution { void backtracking(vectorint factors, vectorvectorint 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: vectorvectorint getFactors(int n) { vectorint factors {n}; vectorvectorint ans; backtracking(factors, ans); return ans; } };JavaScriptclass 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(Listint factors, ListIListint ans) { // Got a solution. if (factors.Count 1) { ans.Add(new Listint(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 IListIListint GetFactors(int n) { ListIListint ans new ListIListint(); Backtracking(new Listint { n }, ans); return ans; } }Gofunc 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 }Kotlinclass Solution { private fun backtracking(factors: MutableListInt, ans: MutableListListInt) { // 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): ListListInt { val ans mutableListOfListInt() backtracking(mutableListOf(n), ans) return ans } }Swiftclass 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 } }Rustimpl Solution { pub fn get_factors(n: i32) - VecVeci32 { let mut ans Vec::new(); fn backtracking(factors: mut Veci32, ans: mut VecVeci32) { 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显式栈核心直觉迭代版本用显式栈代替系统递归。栈中的每个元素都存放一份“正在构建的因子列表”。每次弹出一个状态取出其最后一个因子尝试把它拆成两个更小的因子。与回溯版的区别在于迭代版为每个分支新建因子列表而不是修改并恢复同一个列表。这样逻辑更简单、更不容易出错但会占用更多内存。算法步骤用栈初始化[n]准备空的结果列表当栈不为空时循环弹出一个因子列表取出最后一个元素作为lastFactor确定枚举起点若列表为空则从2开始否则从列表中剩余的最后一个因子开始对i从起点遍历到sqrt(lastFactor)若i能整除lastFactor则创建一个新列表保留原剩余因子再追加i与lastFactor / i将新列表压入栈同时加入结果返回结果列表。多语言实现Javaclass Solution { public ListListInteger getFactors(int n) { final ListListInteger ans new LinkedList(); final StackLinkedListInteger stack new Stack(); stack.push(new LinkedList(new LinkedList(Arrays.asList(n)))); while (!stack.isEmpty()) { final LinkedListInteger 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. LinkedListInteger newFactors new LinkedList(factors); newFactors.add(i); newFactors.add(lastFactor / i); stack.push(newFactors); ans.add(new LinkedList(newFactors)); } } } return ans; } }Cclass Solution { public: vectorvectorint getFactors(int n) { vectorvectorint ans; stackvectorint 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) { vectorint newFactors factors; newFactors.push_back(i); newFactors.push_back(lastFactor / i); stack.push(newFactors); ans.push_back(newFactors); } } } return ans; } };JavaScriptclass 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 IListIListint GetFactors(int n) { ListIListint ans new ListIListint(); StackListint stack new StackListint(); stack.Push(new Listint { n }); while (stack.Count 0) { Listint 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) { Listint newFactors new Listint(factors); newFactors.Add(i); newFactors.Add(lastFactor / i); stack.Push(newFactors); ans.Add(new Listint(newFactors)); } } } return ans; } }Gofunc 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 }Kotlinclass Solution { fun getFactors(n: Int): ListListInt { val ans mutableListOfListInt() val stack ArrayDequeMutableListInt() 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 } }Swiftclass 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 } }Rustimpl Solution { pub fn get_factors(n: i32) - VecVeci32 { let mut ans Vec::new(); let mut stack: VecVeci32 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)$ 量级的状态。两种解法对比维度回溯Backtracking迭代 DFS显式栈状态管理复用同一个列表靠“压入—递归—弹出”恢复现场每个分支新建列表互不干扰代码心智负担需理解就地修改与恢复的时机逻辑更直观天然隔离状态时间复杂度$O(n^{1.5})$$O(n^{1.5})$空间复杂度$O(\log n)$$O(n \cdot \log n)$适用场景对内存敏感、追求最优空间想规避递归深度风险、偏好显式栈常见误区Common Pitfalls1. 生成重复组合最常见的错误是产出[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 是回溯思想在数论问题上的经典应用。抓住三个要点即可举一反三去重靠顺序非递减枚举是避免重复组合的通用手段同样适用于 combination-target-sum.md、subsets-ii.md 等组合类问题剪枝靠平方根因子成对的对称性让搜索量从 $O(n)$ 降到 $O(\sqrt{n})$两种 DFS 实现互证递归回溯共享状态 现场恢复与迭代栈分支独立状态在时间上等价空间上各有取舍可作为“递归改迭代”的标准演练。完整题解原文见 factor-combinations.md仓库中还有大量按语言分类的实现可供对照学习如 python、java、javascript、cpp、go 等目录可结合 README.md 中的题目索引快速定位。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 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继续递归。算法步骤用factors [n]初始化并准备一个空的结果列表ans在回溯函数中若factors的元素个数大于 1说明当前组合合法将它的副本加入结果弹出最后一个因子记为lastFactor确定枚举起点若factors为空则从2开始否则从factors中剩余的最后一个因子开始对i从起点遍历到sqrt(lastFactor)若i能整除lastFactor则把i与lastFactor / i压入factors递归再弹出二者完成回溯返回前把lastFactor重新放回factors恢复现场返回结果列表。多语言实现Pythonclass 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 ansJavaclass Solution { private void backtracking(final LinkedListInteger factors, final ListListInteger 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 ListListInteger getFactors(int n) { final ListListInteger ans new LinkedList(); backtracking(new LinkedList(Arrays.asList(n)), ans); return ans; } }Cclass Solution { void backtracking(vectorint factors, vectorvectorint 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: vectorvectorint getFactors(int n) { vectorint factors {n}; vectorvectorint ans; backtracking(factors, ans); return ans; } };JavaScriptclass 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(Listint factors, ListIListint ans) { // Got a solution. if (factors.Count 1) { ans.Add(new Listint(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 IListIListint GetFactors(int n) { ListIListint ans new ListIListint(); Backtracking(new Listint { n }, ans); return ans; } }Gofunc 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 }Kotlinclass Solution { private fun backtracking(factors: MutableListInt, ans: MutableListListInt) { // 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): ListListInt { val ans mutableListOfListInt() backtracking(mutableListOf(n), ans) return ans } }Swiftclass 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 } }Rustimpl Solution { pub fn get_factors(n: i32) - VecVeci32 { let mut ans Vec::new(); fn backtracking(factors: mut Veci32, ans: mut VecVeci32) { 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显式栈核心直觉迭代版本用显式栈代替系统递归。栈中的每个元素都存放一份“正在构建的因子列表”。每次弹出一个状态取出其最后一个因子尝试把它拆成两个更小的因子。与回溯版的区别在于迭代版为每个分支新建因子列表而不是修改并恢复同一个列表。这样逻辑更简单、更不容易出错但会占用更多内存。算法步骤用栈初始化[n]准备空的结果列表当栈不为空时循环弹出一个因子列表取出最后一个元素作为lastFactor确定枚举起点若列表为空则从2开始否则从列表中剩余的最后一个因子开始对i从起点遍历到sqrt(lastFactor)若i能整除lastFactor则创建一个新列表保留原剩余因子再追加i与lastFactor / i将新列表压入栈同时加入结果返回结果列表。多语言实现Javaclass Solution { public ListListInteger getFactors(int n) { final ListListInteger ans new LinkedList(); final StackLinkedListInteger stack new Stack(); stack.push(new LinkedList(new LinkedList(Arrays.asList(n)))); while (!stack.isEmpty()) { final LinkedListInteger 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. LinkedListInteger newFactors new LinkedList(factors); newFactors.add(i); newFactors.add(lastFactor / i); stack.push(newFactors); ans.add(new LinkedList(newFactors)); } } } return ans; } }Cclass Solution { public: vectorvectorint getFactors(int n) { vectorvectorint ans; stackvectorint 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) { vectorint newFactors factors; newFactors.push_back(i); newFactors.push_back(lastFactor / i); stack.push(newFactors); ans.push_back(newFactors); } } } return ans; } };JavaScriptclass 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 IListIListint GetFactors(int n) { ListIListint ans new ListIListint(); StackListint stack new StackListint(); stack.Push(new Listint { n }); while (stack.Count 0) { Listint 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) { Listint newFactors new Listint(factors); newFactors.Add(i); newFactors.Add(lastFactor / i); stack.Push(newFactors); ans.Add(new Listint(newFactors)); } } } return ans; } }Gofunc 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 }Kotlinclass Solution { fun getFactors(n: Int): ListListInt { val ans mutableListOfListInt() val stack ArrayDequeMutableListInt() 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 } }Swiftclass 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 } }Rustimpl Solution { pub fn get_factors(n: i32) - VecVeci32 { let mut ans Vec::new(); let mut stack: VecVeci32 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)$ 量级的状态。两种解法对比维度回溯Backtracking迭代 DFS显式栈状态管理复用同一个列表靠“压入—递归—弹出”恢复现场每个分支新建列表互不干扰代码心智负担需理解就地修改与恢复的时机逻辑更直观天然隔离状态时间复杂度$O(n^{1.5})$$O(n^{1.5})$空间复杂度$O(\log n)$$O(n \cdot \log n)$适用场景对内存敏感、追求最优空间想规避递归深度风险、偏好显式栈常见误区Common Pitfalls1. 生成重复组合最常见的错误是产出[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 是回溯思想在数论问题上的经典应用。抓住三个要点即可举一反三去重靠顺序非递减枚举是避免重复组合的通用手段同样适用于 combination-target-sum.md、subsets-ii.md 等组合类问题剪枝靠平方根因子成对的对称性让搜索量从 $O(n)$ 降到 $O(\sqrt{n})$两种 DFS 实现互证递归回溯共享状态 现场恢复与迭代栈分支独立状态在时间上等价空间上各有取舍可作为“递归改迭代”的标准演练。完整题解原文见 factor-combinations.md仓库中还有大量按语言分类的实现可供对照学习如 python、java、javascript、cpp、go 等目录可结合 README.md 中的题目索引快速定位。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考