LeetCode 254 - Factor Combinations

LeetCode Problem 254

Difficulty: 🟡 Medium
Topics: Backtracking

Solution

Problem Understanding

The problem asks us to generate every unique way to express a number n as a product of integers greater than 1 and less than n.

A factor combination is a list of integers whose product equals n. The order inside a combination does not matter. For example, for 12, the combinations [2, 6] and [6, 2] represent the same factorization, so only one of them should appear in the result.

The input is a single integer n, and the output is a list of lists. Each inner list contains factors whose multiplication equals n.

The constraint 1 <= n <= 10^7 is important because it rules out extremely expensive brute-force enumeration of all possible sequences. However, the input is still small enough that recursive backtracking with pruning is efficient.

There are several edge cases that are important to recognize early:

• If n = 1, there are no valid factorizations because the allowed factors must be in the range [2, n - 1].
• If n is prime, the result is empty because prime numbers have no non-trivial factors.
• Repeated factors must be handled correctly. For example, 16 can produce [2,2,2,2], [2,2,4], [2,8], and [4,4].
• Duplicate combinations must be avoided. The algorithm should not produce both [2,6] and [6,2].

The key challenge is generating all valid combinations efficiently while avoiding duplicates.

Approaches

Brute Force Approach

A brute-force strategy would try every possible combination of integers from 2 to n - 1, checking whether their product equals n.

For example, for n = 12, we could attempt every possible sequence such as:

• [2,2,3]
• [2,3,2]
• [3,2,2]
• [2,6]
• [6,2]

We would then filter out invalid or duplicate combinations.

This works because eventually every valid factorization is explored. However, it is extremely inefficient because the number of candidate sequences grows exponentially. Most generated combinations do not multiply to n, and many valid factorizations appear multiple times in different orders.

The brute-force method becomes impractical even for moderately large values of n.

Optimal Approach, Backtracking with Factor Pruning

The key insight is that factor combinations naturally form a recursive structure.

If a number n is divisible by some factor f, then the remaining problem becomes finding factor combinations of n / f.

For example:

• 12 = 2 × 6
• Now factorize 6
• 6 = 2 × 3

This gives [2,2,3].

Another important observation is that combinations should be generated in non-decreasing order. If we only allow future factors to be greater than or equal to the current factor, we automatically avoid duplicates.

For example:

• Allow [2,6]
• Do not allow [6,2]

We also only need to search factors up to sqrt(current_number) because factors larger than the square root must pair with a smaller factor that has already been considered.

This dramatically reduces the search space.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential, approximately O(2^n) in practice	O(n)	Tries many invalid and duplicate combinations
Optimal	O(k * sqrt(n)) approximately	O(log n) recursion depth, excluding output	Uses recursive factor decomposition with pruning

Algorithm Walkthrough

1. Initialize an empty result list that will store all valid factor combinations.
2. Create a recursive backtracking function with three parameters:

• remaining, the current number we still need to factorize
• start_factor, the smallest factor we are allowed to use next
• current_path, the current combination being built

3. Inside the recursive function, iterate through all possible factors from start_factor up to sqrt(remaining).
4. For each candidate factor:

• Check whether it divides remaining.
• If remaining % factor == 0, then it is a valid factor.

5. When a valid factor is found:

• Append the factor to the current path.
• The complementary factor is remaining // factor.

6. At this point, we already have a valid factor combination:

• current_path + [complement]
• Add this combination to the result list.

7. Continue exploring deeper factorizations recursively:

• Call the recursive function on remaining // factor
• Use factor again as the new minimum allowed factor
• This allows repeated factors like [2,2,2,2]

8. After recursion finishes, remove the last factor from the path to backtrack and explore other possibilities.
9. Continue until all factors have been explored.

Why it works

The algorithm maintains an important invariant: factors in current_path are always in non-decreasing order.

Because of this property:

• Every valid combination is generated exactly once.
• Duplicate permutations are impossible.
• Recursive decomposition guarantees that every factorization of n is eventually explored.

The square-root bound ensures we never miss any factor pair because every larger factor must pair with a smaller factor already checked earlier.

Python Solution

from typing import List
import math

class Solution:
    def getFactors(self, n: int) -> List[List[int]]:
        result = []

        def backtrack(remaining: int, start_factor: int, path: List[int]) -> None:
            limit = int(math.sqrt(remaining)) + 1

            for factor in range(start_factor, limit):
                if remaining % factor == 0:
                    complement = remaining // factor

                    result.append(path + [factor, complement])

                    path.append(factor)
                    backtrack(complement, factor, path)
                    path.pop()

        backtrack(n, 2, [])

        return result

After the code block, it is helpful to connect each section of the implementation to the recursive strategy.

The result list stores every valid factor combination discovered during the search.

The backtrack helper function performs the recursive exploration. The remaining parameter represents the portion of the number that still needs factorization. The start_factor parameter enforces non-decreasing order, which prevents duplicates. The path list stores the current partial combination.

The loop only searches up to sqrt(remaining). If a factor larger than the square root exists, its paired smaller factor must already have been processed.

Whenever a valid factor is found, the algorithm immediately constructs a complete combination using the complementary factor. For example, if remaining = 12 and factor = 2, the complement is 6, producing [2,6].

The recursive call then continues breaking down the complement further. This is how combinations like [2,2,3] are discovered.

The path.pop() statement is the backtracking step. It restores the previous state so the algorithm can explore other factor choices independently.

Go Solution

package main

import "math"

func getFactors(n int) [][]int {
	var result [][]int

	var backtrack func(remaining int, startFactor int, path []int)

	backtrack = func(remaining int, startFactor int, path []int) {
		limit := int(math.Sqrt(float64(remaining)))

		for factor := startFactor; factor <= limit; factor++ {
			if remaining%factor == 0 {
				complement := remaining / factor

				combination := append([]int{}, path...)
				combination = append(combination, factor, complement)
				result = append(result, combination)

				path = append(path, factor)
				backtrack(complement, factor, path)
				path = path[:len(path)-1]
			}
		}
	}

	backtrack(n, 2, []int{})

	return result
}

The Go implementation follows the same recursive logic as the Python version, but there are some language-specific considerations.

Slices in Go are references to underlying arrays, so when storing a combination in result, we must create a copy using append([]int{}, path...). Without copying, later modifications during backtracking would corrupt previously stored results.

The recursion depth remains small because each recursive step divides the remaining value by at least 2.

Go also requires explicit conversion between float64 and int when using math.Sqrt.

Worked Examples

Example 1

Input:

n = 1

There are no integers in the range [2, n - 1].

Result:

[]

No recursive exploration occurs because the initial loop range is empty.

Example 2

Input:

n = 12

Initial call:

backtrack(12, 2, [])

Step	Remaining	Factor	Path	Action
1	12	2	[]	12 % 2 == 0
2	12	2	[]	Add [2,6]
3	6	2	[2]	Recursive call
4	6	2	[2]	6 % 2 == 0
5	6	2	[2]	Add [2,2,3]
6	3	2	[2,2]	Recursive call ends immediately
7	12	3	[]	12 % 3 == 0
8	12	3	[]	Add [3,4]

Final result:

[[2,6],[2,2,3],[3,4]]

Example 3

Input:

n = 37

Initial call:

backtrack(37, 2, [])

The algorithm checks factors from 2 through 6.

None divide 37.

Result:

[]

Since 37 is prime, no valid combinations exist.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(k * sqrt(n)) approximately	Each recursive level checks factors up to square root
Space	O(log n) excluding output	Recursion depth is bounded by repeated division

The exact running time depends on the number of factor combinations generated. Highly composite numbers produce more recursive branches than prime numbers.

The recursion depth is logarithmic because each recursive step reduces the remaining value by at least a factor of 2. The output itself may contain many combinations, which is unavoidable because all valid factorizations must be returned.

Test Cases

from typing import List
import math

class Solution:
    def getFactors(self, n: int) -> List[List[int]]:
        result = []

        def backtrack(remaining: int, start_factor: int, path: List[int]) -> None:
            limit = int(math.sqrt(remaining)) + 1

            for factor in range(start_factor, limit):
                if remaining % factor == 0:
                    complement = remaining // factor

                    result.append(path + [factor, complement])

                    path.append(factor)
                    backtrack(complement, factor, path)
                    path.pop()

        backtrack(n, 2, [])

        return result

solution = Solution()

assert solution.getFactors(1) == []  # minimum input
assert solution.getFactors(37) == []  # prime number
assert sorted(solution.getFactors(12)) == sorted([[2, 6], [2, 2, 3], [3, 4]])  # example case
assert sorted(solution.getFactors(16)) == sorted([
    [2, 8],
    [2, 2, 4],
    [2, 2, 2, 2],
    [4, 4]
])  # repeated factors
assert sorted(solution.getFactors(32)) == sorted([
    [2, 16],
    [2, 2, 8],
    [2, 2, 2, 4],
    [2, 2, 2, 2, 2],
    [2, 4, 4],
    [4, 8]
])  # many decompositions
assert solution.getFactors(2) == []  # smallest prime
assert sorted(solution.getFactors(100)) == sorted([
    [2, 50],
    [2, 2, 25],
    [2, 2, 5, 5],
    [2, 5, 10],
    [4, 25],
    [4, 5, 5],
    [5, 20],
    [10, 10]
])  # multiple branching paths

Test	Why
n = 1	Verifies empty result for smallest input
n = 37	Verifies handling of prime numbers
n = 12	Validates standard mixed factorization
n = 16	Tests repeated factors and deep recursion
n = 32	Tests multiple recursive branches
n = 2	Tests smallest prime edge case
n = 100	Tests complex composite number

Edge Cases

Input Equals 1

When n = 1, there are no valid factors because the allowed factor range is [2, n - 1], which is empty. A naive implementation might accidentally include [1] or attempt invalid recursion. This implementation correctly returns an empty list because the initial factor loop never executes.

Prime Numbers

Prime numbers such as 37 have no non-trivial divisors. Some implementations incorrectly include the number itself as a factor pair. This solution avoids that mistake because the search only checks factors from 2 through sqrt(n), and combinations only form when a valid divisor exists.

Repeated Factors

Numbers like 16 require repeated use of the same factor:

16 = 2 × 2 × 2 × 2

A common bug is preventing reuse of factors after they appear once. This implementation avoids the issue by passing the current factor as the next start_factor, allowing repeated selections while still preventing duplicate permutations.

Duplicate Permutations

Without ordering constraints, the algorithm could generate both [2,6] and [6,2]. This implementation enforces non-decreasing order by never allowing recursive calls to use factors smaller than the current one. As a result, each unique combination appears exactly once.