# Factor Combinations

## Question ([LC.254](https://leetcode.com/problems/factor-combinations/))

> Find all possible factor combinations of a number.

## Example

```
I: 8
O: [ [2,2,2], [2,4] ]
I: 1
O: []
I: 2
O: []
I: 9
O: [ [3,3] ]
```

Assume n > 0. How large can n get? n cannot be very large.\
what about 1? 1x1x1... Assume factors greater than 1.

## Attempt #1

```
1. Define subproblem
    factorSearch(result, factors, dividend) => 
    add all factor combinations of dividend to result (with given prefix factors)
2. Recursive calls
    for factor from 2 to dividend / 2
        if (divident % factor != 0) continue
        factorSearch(result, factors.add(factor), divident / factor)
3. Bases cases
    if (dividend == 1)
        result.add(new List(factors))
```

What's wrong with this approach?

```
I: 12
O: [[2,2,3],[2,3,2],[2,6],[3,2,2],[3,4],[4,3],[6,2]]
E: [[2,6],[3,4],[2,2,3]]
```

We need to choose representative for each combination. Sorted is the easiest to work with. We want to put in the smallest factor as much as possible before we move on to a larger factor.

## Corrected Code

```java
public List<List<Integer>> getFactors(int n) {
    List<List<Integer>> result = new ArrayList<>();
    if (n < 3) {
        return result;
    }
    List<Integer> factors = new ArrayList<>();
    factorSearch(result, factors, n, 2);
    return result;
}

private void factorSearch(List<List<Integer>> result, 
                          List<Integer> factors, 
                          int dividend, 
                          int startFactor) {
    // base case
    if (dividend == 1 && factors.size() > 1) {
        result.add(new ArrayList<>(factors));
        return;
    }
    // search
    for (int factor = startFactor; factor < dividend + 1; factor++) {
        if (dividend % factor != 0) {
            continue;
        }
        factors.add(factor);
        factorSearch(result, factors, dividend / factor, factor);
        factors.remove(factors.size() - 1);
    }
}
```

## Time & Space Complexity

Time O(n\*2^n) Space O(n)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zedive.gitbook.io/project-l/part-2/graph-search/exhaustive-search/factor-combinations.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.