LeetCode 254: Factor Combinations

Problem Restatement

We are given a positive integer n.

We need to return all possible ways to write n as a product of factors.

Each factor must be between 2 and n - 1.

For example:

8 = 2 * 2 * 2
8 = 2 * 4

So for n = 8, valid answers are:

[[2, 2, 2], [2, 4]]

We may return the combinations in any order. The constraint is 1 <= n <= 10^7.

Input and Output

Example function shape:

def getFactors(n: int) -> list[list[int]]:
    ...

Examples

Example 1:

n = 1

There are no factors between 2 and 0.

Answer:

[]

Example 2:

n = 12

Valid factorizations are:

12 = 2 * 6
12 = 3 * 4
12 = 2 * 2 * 3

Answer:

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

Example 3:

n = 37

37 is prime, so it has no valid factor combination.

Answer:

[]

First Thought: Try Every Product

A direct brute force idea is to generate many possible lists of numbers and check whether their product equals n.

For example, for n = 12, we might try:

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

Then we keep only the lists whose product is 12.

This approach is hard to control. We do not know the length of each factor list in advance, and generating arbitrary products creates many useless candidates.

Problem With Brute Force

The search space grows quickly.

Instead of generating all possible lists, we should build only lists that still divide n.

If a number does not divide the remaining value, it cannot appear next in the factorization.

This leads naturally to DFS backtracking.

Key Insight

A factorization can be built step by step.

Suppose:

n = 12

If we choose factor 2, the remaining value becomes:

12 // 2 = 6

Now the problem becomes:

Find factor combinations of 6, but do not use factors smaller than 2.

This gives:

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

The important rule is to build combinations in non-decreasing order.

That means:

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

are allowed, but duplicates such as:

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

are never generated.

We enforce this by passing a start value into DFS. Each next factor must be at least start.

Algorithm

Use a recursive function:

dfs(remaining, start, path)

where:

At each call:

1. Try every factor factor from start up to sqrt(remaining).
2. If factor divides remaining, then we found a valid pair:

   factor * (remaining // factor)
3. Add:

   path + [factor, remaining // factor]
   to the answer.
4. Recurse into:

   dfs(remaining // factor, factor, path + [factor])

The recursive call allows the quotient to be broken down further.

Walkthrough

Use:

n = 12

Start:

dfs(12, 2, [])

Try factor = 2.

Since 12 % 2 == 0, we get:

[2, 6]

Add it to the answer.

Then recurse:

dfs(6, 2, [2])

Inside this call, try factor = 2.

Since 6 % 2 == 0, we get:

[2, 2, 3]

Add it to the answer.

Then recurse:

dfs(3, 2, [2, 2])

No factor from 2 to sqrt(3) divides 3, so this path ends.

Back at the first call, try factor = 3.

Since 12 % 3 == 0, we get:

[3, 4]

Add it to the answer.

The final result is:

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

Correctness

The algorithm only adds combinations whose product is n.

At each step, path contains factors already chosen. The variable remaining is exactly the value that must still be multiplied into the product. When we find a divisor factor of remaining, the pair:

factor, remaining // factor

multiplies back to remaining.

Therefore:

path + [factor, remaining // factor]

multiplies back to the original n.

The algorithm does not generate duplicate permutations because every recursive call keeps the next factor at least as large as the previous factor. So combinations are generated only in non-decreasing order.

The algorithm does not miss any valid combination. Any valid factor combination can be sorted into non-decreasing order. Its first factor must be at least 2 and at most sqrt(remaining) unless the combination has only one remaining factor, which is handled when we append remaining // factor. DFS tries every possible next factor in this allowed range, so it eventually follows the exact sequence of factors for every valid combination.

Therefore the algorithm returns exactly all valid factor combinations.

Complexity

Let A be the number of valid factor combinations returned.

There is no simple tight polynomial bound only in terms of n, because the output size depends on the number of factor combinations.

Implementation

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

        def dfs(remaining: int, start: int, path: list[int]) -> None:
            factor = start

            while factor * factor <= remaining:
                if remaining % factor == 0:
                    quotient = remaining // factor

                    ans.append(path + [factor, quotient])

                    dfs(quotient, factor, path + [factor])

                factor += 1

        dfs(n, 2, [])
        return ans

Code Explanation

We store the final answer here:

ans = []

The DFS state is:

dfs(remaining, start, path)

The loop only needs to try factors up to the square root of remaining:

while factor * factor <= remaining:

If factor is larger than the square root, then its matching quotient is smaller than factor. That pair would already have been considered in the opposite order.

When a factor divides the remaining value:

if remaining % factor == 0:

we compute the matching quotient:

quotient = remaining // factor

Then we add the current complete factorization:

ans.append(path + [factor, quotient])

After that, we continue factoring the quotient:

dfs(quotient, factor, path + [factor])

We pass factor as the new start, so future factors cannot be smaller. This keeps combinations in non-decreasing order.

Testing

def normalize(result: list[list[int]]) -> list[list[int]]:
    return sorted(sorted(row) for row in result)

def run_tests():
    s = Solution()

    assert normalize(s.getFactors(1)) == []
    assert normalize(s.getFactors(37)) == []
    assert normalize(s.getFactors(8)) == normalize([[2, 4], [2, 2, 2]])
    assert normalize(s.getFactors(12)) == normalize([[2, 6], [3, 4], [2, 2, 3]])
    assert normalize(s.getFactors(16)) == normalize([[2, 8], [2, 2, 4], [2, 2, 2, 2], [4, 4]])
    assert normalize(s.getFactors(32)) == normalize([
        [2, 16],
        [2, 2, 8],
        [2, 2, 2, 4],
        [2, 2, 2, 2, 2],
        [2, 4, 4],
        [4, 8],
    ])

    print("all tests passed")

run_tests()

Test meaning: