NeetCode #514LC-254MediumBacktrackingNC Algo100
← Back to All Problems#514 · #254 · Factor Combinations(因子的组合)
📌 Problem Statement & Constraints
Numbers can be expressed as products of their factors. Given an integer
n, return all possible factor combinations of n using factors greater than 1. Constraints: 1 <= n <= 10^7.💡 Core Algorithmic Approaches
- Recursively try divisors
fstarting fromstartup tosqrt(remain). - When
fdividesremain, the combination ispath + [f]plus the cofactorremain / f, which is a valid combination with at least two factors. - Recurse with
start = f(allowing repeated factors) andremain / f. - Excluding
nitself from the results is automatic, since a combination always contains at least two factors.
💻 Benchmark Python3 Implementation
class Solution:
def getFactors(self, n: int) -> List[List[int]]:
res = []
def dfs(start: int, remain: int, path: List[int]) -> None:
f = start
while f * f <= remain: # only need divisors up to sqrt
if remain % f == 0:
path.append(f)
# [path..., f, remain // f] is a valid combination
res.append(path[:] + [remain // f])
# recurse with the cofactor, allowing further factors >= f
dfs(f, remain // f, path)
path.pop()
f += 1
dfs(2, n, [])
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(sqrt(n) * number of combinations).
💾 Space Complexity
O(log n) for the recursion depth.
⚠️ Interview Pitfalls & Follow-ups
- Iterating up to
remaininstead ofsqrt(remain): the loop would be far too slow. - Recursing with
start = f + 1: repeated factors such as2 * 2 * 2would be excluded. - Including the trivial combination
[n]: the problem excludes it; the construction always produces at least two factors. - Forgetting
path.pop(): the path would leak between branches.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.