⚡Flashcard Drill➔
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

  1. Recursively try divisors f starting from start up to sqrt(remain).
  2. When f divides remain, the combination is path + [f] plus the cofactor remain / f, which is a valid combination with at least two factors.
  3. Recurse with start = f (allowing repeated factors) and remain / f.
  4. Excluding n itself 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 remain instead of sqrt(remain): the loop would be far too slow.
  • Recursing with start = f + 1: repeated factors such as 2 * 2 * 2 would 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.
🎯 Drill This Card Now➔

🧩 Related Backtracking Problems