Factor Combinations solution and explanation
7 more videos on this problem
LeetCode 254: Factor CombinationsKevin Dai · 3:55 · 3K views
Leetcode 254. Factor Combinations. 详细解析Alina L · 16:10 · 2K views
Leetcode 254. Factor Combinations (backtracking)LetsCode · 9:38 · 1K views
Factor Combinations (Medium), C++, LeetcodeH William Polenz · 32:30 · 863 views
Leetcode Algorithm III day 11 | 254. Factor Combinations 中文Code Learning · 0:59 · 272 views
LeetCode Medium: 254. Factor Combinationsrobzingcod · 42:02 · 106 views
LeetCode 254: Factor CombinationsAlitaCode · 26:48 · 59 views
139. Word Break，254. Factor Combinations，329. Longest Increase--leetcode[中文]python&java---动态规划3.9日Qiping Ran · 59:35 · 41 views
The problem
Numbers can be regarded as the product of their factors.
- For example,
8 = 2 x 2 x 2 = 2 x 4.
Given an integer n, return all possible combinations of its factors. You may return the answer in any order.
Note that the factors should be in the range [2, n - 1].
Example 1:
Input: n = 1 Output: []
Example 2:
Input: n = 12 Output: [[2,6],[3,4],[2,2,3]]
Example 3:
Input: n = 37 Output: []
Constraints:
1 <= n <= 107
Approach overview
Problem Overview: Given an integer n, return all unique combinations of factors (excluding 1 and n) whose product equals n. Each combination should contain factors greater than 1 and appear in non‑decreasing order.
Approach 1: Factor Enumeration + Recursive Backtracking (O(sqrt(n) * k) time, O(k) space)
The natural way to generate factor combinations is backtracking. Start from the smallest factor (2) and iterate upward while the current factor divides n. When a valid divisor i is found, append it to the current path and recursively continue searching for factors of n / i. This builds combinations incrementally while maintaining non‑decreasing order by always starting the next search from i. Each recursion explores deeper factor splits until the remaining value becomes 1 or no further divisors exist.
The key pruning step limits iteration to factors up to sqrt(n). If i divides n, the complementary factor n / i automatically forms a valid pair. That pair can be appended directly to the current path to produce a valid combination without exploring redundant permutations. This significantly reduces the search space compared to testing all integers up to n.
This pattern is a classic use of backtracking: maintain a temporary list, try a candidate factor, recurse on the reduced number, then backtrack by removing the factor. The recursion tree naturally enumerates all valid multiplicative partitions. The number of results (k) depends on the factor structure of n, so runtime scales with both divisor checks and generated combinations.
Approach 2: Optimized Backtracking with Start Pointer (O(sqrt(n) * k) time, O(k) space)
A small optimization keeps a start pointer representing the smallest factor allowed in the current recursion level. This prevents permutations like [2,6] and [6,2] from appearing separately. The algorithm iterates from start to sqrt(remaining), checks divisibility, and recurses with the reduced value. Each valid divisor produces two results: the pair itself and deeper decompositions.
The recursion depth is bounded by the number of factors in a combination, so auxiliary space remains proportional to the path length. This method works well for factor partition problems and appears frequently alongside other recursive enumeration techniques like depth-first search and recursion.
Recommended for interviews: Interviewers typically expect the optimized backtracking approach with a start index and a sqrt(n) bound. It demonstrates control over recursion, pruning, and duplicate avoidance. Showing the naive divisor exploration first proves understanding, but the pruned backtracking version shows strong problem‑solving skill.
Solution
class Solution:
def getFactors(self, n: int) -> List[List[int]]:
def dfs(n, i):
if t:
ans.append(t + [n])
j = i
while j * j <= n:
if n % j == 0:
t.append(j)
dfs(n // j, j)
t.pop()
j += 1
t = []
ans = []
dfs(n, 2)
return ansclass Solution {
private List<Integer> t = new ArrayList<>();
private List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> getFactors(int n) {
dfs(n, 2);
return ans;
}
private void dfs(int n, int i) {
if (!t.isEmpty()) {
List<Integer> cp = new ArrayList<>(t);
cp.add(n);
ans.add(cp);
}
for (int j = i; j <= n / j; ++j) {
if (n % j == 0) {
t.add(j);
dfs(n / j, j);
t.remove(t.size() - 1);
}
}
}
}class Solution {
public:
vector<vector<int>> getFactors(int n) {
vector<int> t;
vector<vector<int>> ans;
function<void(int, int)> dfs = [&](int n, int i) {
if (t.size()) {
vector<int> cp = t;
cp.emplace_back(n);
ans.emplace_back(cp);
}
for (int j = i; j <= n / j; ++j) {
if (n % j == 0) {
t.emplace_back(j);
dfs(n / j, j);
t.pop_back();
}
}
};
dfs(n, 2);
return ans;
}
};func getFactors(n int) [][]int {
t := []int{}
ans := [][]int{}
var dfs func(n, i int)
dfs = func(n, i int) {
if len(t) > 0 {
ans = append(ans, append(slices.Clone(t), n))
}
for j := i; j <= n/j; j++ {
if n%j == 0 {
t = append(t, j)
dfs(n/j, j)
t = t[:len(t)-1]
}
}
}
dfs(n, 2)
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Factor Enumeration | O(n * k) | O(k) | Simple conceptual approach for understanding factor generation |
| Backtracking with Factor Checks | O(sqrt(n) * k) | O(k) | General solution for generating all factor combinations |
| Optimized Backtracking with Start Pointer | O(sqrt(n) * k) | O(k) | Preferred interview solution that avoids duplicate permutations |
Frequently asked questions
Is Factor Combinations easy or hard?
Factor Combinations is generally classified as a Medium problem. The challenge comes from designing a recursive backtracking process that avoids duplicates and prunes the search using sqrt(n). Developers familiar with DFS-style enumeration usually solve it quickly.
Factor Combinations Python/Java solution
Python, Java, C++, and Go implementations follow the same pattern: maintain a list for the current path, iterate from a starting factor to sqrt(n), check divisibility, append the factor, recurse on n / factor, then backtrack. Each valid divisor also forms a combination with its complementary factor.
How to solve Factor Combinations in O(n)?
An exact O(n) solution generally doesn't exist because the algorithm must generate every valid factor combination. The practical optimization limits divisor checks to sqrt(n) and uses backtracking to explore only valid branches. This reduces unnecessary exploration while still enumerating all results.
What is the best approach for Factor Combinations?
Backtracking with a start index and a sqrt(n) bound is the standard solution. It recursively builds factor combinations while ensuring factors appear in non‑decreasing order. This avoids duplicates and reduces the search space by only checking divisors up to sqrt(n).
Is Factor Combinations asked at Google/Amazon/Meta?
Factor combination generation appears in interviews at companies like Google, Amazon, and Meta as a recursion or backtracking exercise. It tests divisor logic, pruning strategies, and the ability to avoid duplicate permutations during recursive enumeration.
What data structure is used in Factor Combinations?
The main structure is a dynamic list or array used as a recursion path to store the current factor combination. The algorithm also relies on recursion (call stack) to explore deeper factor partitions. No advanced structures like heaps or hash maps are required.
What is the time complexity of Factor Combinations?
The typical backtracking solution runs in roughly O(sqrt(n) * k), where k is the number of valid factor combinations produced. Each recursion step checks divisibility only up to sqrt of the remaining number. Space complexity is O(k) due to recursion depth and the temporary path used to build combinations.