## Question

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

.

## Algorithm

A similar to combination sum question.

First I used bottom up method to get the product from 1, but got TLE when the number is quite big;

So I checked the standard answer and turn to bottom down use backtracking.

## Code

class Solution { public List<List<Integer>> getFactors(int n) { List<List<Integer>> res = new ArrayList<>(); if (n < 2) { return res; } helper(res, n, 2, new ArrayList<>()); return res; } private void helper(List<List<Integer>> res, int n, int index, List<Integer> list) { if (n == 1 && list.size() > 1) { res.add(new ArrayList<>(list)); } for (int i = index; i <= n; i++) { if (n % i == 0) { list.add(i); helper(res, n/i, i, list); list.remove(list.size() - 1); } } } }

- Space complexity: output: O(n), the space for saving the Internal products: O(log(n))
- Time complexity: For the number of solutions, according to this, can be considered as O(n). And inside the loop to find the next n, we do the
`n/I`

each time, the time is O(n^0.5). So in total it's O(n^1.5).