# 问题 原题链接：[https://leetcode.com/problems/factor-combinations/](https://leetcode.com/problems/factor-combinations/) Numbers can be regarded as product of its factors. For example, ``` 8 = 2 x 2 x 2; = 2 x 4. ``` Write a function that takes an integer n and return all possible combinations of its factors. Note: - Each combination's factors must be sorted ascending, for example: The factors of 2 and 6 is [2, 6], not [6, 2]. - You may assume that n is always positive. Factors should be greater than 1 and less than n. Example 1: ``` input: 1 output: [] ``` Example 2: ``` input: 37 output: [] ``` Example 3: ``` input: 12 output: [ [2, 6], [2, 2, 3], [3, 4] ] ``` Example 4: ``` input: 32 output: [ [2, 16], [2, 2, 8], [2, 2, 2, 4], [2, 2, 2, 2, 2], [2, 4, 4], [4, 8] ] ``` # 分析过程 - 输入：一个正整数 value - 输出：这个正整数的所有因数组合，不包括 1 和自己 - 思路：可以用普通递归的方法，或者回溯法。 - 从 2 开始遍历找因数，然后递归找到 value / factor 的所有组合，然后把 factor 插在第一个即可。这里要去掉重复的情况，见注释。 - 回溯法，见注释。 # 解决方法 普通方法： ```swift class Solution { func getFactors(_ n: Int) -> [[Int]] { // 循环时从2到根号value循环，小于4的结果直接排除 let sqrtValue = Int(sqrtf(Float(n))) guard sqrtValue >= 2 else { return [] } var result = [[Int]]() for f in 2...sqrtValue { // f是因数 guard n % f == 0 else { continue } // 先把f和value/f这种情况放入结果 result.append([f, n / f]) // 对value/f递归，得到所有组合情况 let r = getFactors(n / f) // 处理其他情况 for var v in r { // 题目要求因数重小到大，因此f只能插在最前面 // 还可以过滤掉一些仅仅是顺序不同的重复的情况 guard f <= v[0] else { continue } v.insert(f, at: 0) result.append(v) } } return result } } ``` 回溯法： ```swift class Solution { func _getFactors(value: Int, factor: Int, tmp: inout [Int], result: inout [[Int]]) { guard value > 1 else { // 递归的结束条件，除到1为止 // 这里大于1是为了过滤掉自己本身作为唯一因数这种情况 if tmp.count > 1 { // 除到1以后，tmp里就是一种结果，放入result result.append(tmp) } return } guard value >= factor else { return } for f in factor...value { // f是因数 guard value % f == 0 else { continue } // 把因数放入 tmp.append(f) // 然后对value/f递归 _getFactors(value: value / f, factor: f, tmp: &tmp, result: &result) // 递归结束以后，当前因数的情况就结束了 // 弹出当前因数，继续下一次循环 tmp.removeLast() } } func getFactors(_ n: Int) -> [[Int]] { if n < 4 { return [] } var result = [[Int]]() // 用于回溯的临时空间 var tmp = [Int]() _getFactors(value: n, factor: 2, tmp: &tmp, result: &result) return result } } ```