# 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:

```python
8 = 2 * 2 * 2
8 = 2 * 4
```

So for `n = 8`, valid answers are:

```python
[[2, 2, 2], [2, 4]]
```

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

## Input and Output

| Item | Meaning |
|---|---|
| Input | A positive integer `n` |
| Output | All factor combinations of `n` |
| Factor range | Each factor must be in `[2, n - 1]` |
| Order | Answer may be returned in any order |

Example function shape:

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

## Examples

Example 1:

```python
n = 1
```

There are no factors between `2` and `0`.

Answer:

```python
[]
```

Example 2:

```python
n = 12
```

Valid factorizations are:

```python
12 = 2 * 6
12 = 3 * 4
12 = 2 * 2 * 3
```

Answer:

```python
[[2, 6], [3, 4], [2, 2, 3]]
```

Example 3:

```python
n = 37
```

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

Answer:

```python
[]
```

## 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:

```python
[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:

```python
n = 12
```

If we choose factor `2`, the remaining value becomes:

```python
12 // 2 = 6
```

Now the problem becomes:

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

This gives:

```python
[2, 6]
[2, 2, 3]
```

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

That means:

```python
[2, 6]
[2, 2, 3]
[3, 4]
```

are allowed, but duplicates such as:

```python
[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:

```python
dfs(remaining, start, path)
```

where:

| Variable | Meaning |
|---|---|
| `remaining` | The part of `n` still not factored |
| `start` | Smallest factor allowed next |
| `path` | Factors already chosen |

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:
   ```python id="fgehse"
   factor * (remaining // factor)
   ```
3. Add:
   ```python id="mc6n61"
   path + [factor, remaining // factor]
   ```
   to the answer.
4. Recurse into:
   ```python id="w687or"
   dfs(remaining // factor, factor, path + [factor])
   ```

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

## Walkthrough

Use:

```python
n = 12
```

Start:

```python
dfs(12, 2, [])
```

Try `factor = 2`.

Since `12 % 2 == 0`, we get:

```python
[2, 6]
```

Add it to the answer.

Then recurse:

```python
dfs(6, 2, [2])
```

Inside this call, try `factor = 2`.

Since `6 % 2 == 0`, we get:

```python
[2, 2, 3]
```

Add it to the answer.

Then recurse:

```python
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:

```python
[3, 4]
```

Add it to the answer.

The final result is:

```python
[[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:

```python
factor, remaining // factor
```

multiplies back to `remaining`.

Therefore:

```python
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.

| Metric | Value | Why |
|---|---|---|
| Time | Output-sensitive | We must generate every valid combination |
| Search overhead | About `O(sqrt(n))` per DFS layer in the direct version |
| Space | `O(log n)` recursion depth, excluding output | Each factor is at least `2`, so depth is bounded by repeated division by `2` |

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

## Implementation

```python
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:

```python
ans = []
```

The DFS state is:

```python
dfs(remaining, start, path)
```

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

```python
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:

```python
if remaining % factor == 0:
```

we compute the matching quotient:

```python
quotient = remaining // factor
```

Then we add the current complete factorization:

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

After that, we continue factoring the quotient:

```python
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

```python
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:

| Test | Why |
|---|---|
| `1` | No valid factors |
| Prime number | Should return empty list |
| `8` | Simple repeated factor |
| `12` | Multiple factorization shapes |
| `16` | Powers create deeper recursion |
| `32` | Checks longer repeated-factor chains |