# Share a bit the thought process - short Java 3 ms (Bottom up) and (Top Down)

1. Let's consider how to find a list of candidates that forms n1*n2=n, let's call [n1,n2] a 2-tuple, we loop from 2 to sqrt(n) and find all n1 that is a factor of n, then n2=n/n1. n1<n2 always.

2. how to build our solution that from above sub-problem? Essentially you ask all the N-tuples that can multiply to n. and N-tuple is made up by N-1-tuple plus one number. Above described process is clearly a recursion, and the termination condition is you've tried all combinations.

3. But what forms the combination? suppose a number n%i==0, a full set would be

• 2-tuple, [i, n/i]
• N-tuple (N>2) eg. [i, all N-tuples of (n/i)]

So below is the bottom up approach

``````public List<List<Integer>> getFactors(int n) {
return getFactors(n, 2);
}

private List<List<Integer>> getFactors(int n, int min) {

int end = (int) Math.sqrt(n);
for (int i = min; i <= end; i++) {
if (n % i != 0) continue;

List<List<Integer>> prev = getFactors(n / i, i);
}

return list;
}
``````

And top down using stack.

``````public List<List<Integer>> getFactors(int n) {

List<List<Integer>> res = new ArrayList<>();
combination(n, 2, new Stack<>(), res);
return res;
}

public void combination(int n, int start, Stack<Integer> stack, List<List<Integer>> res) {

int end = (int) Math.sqrt(n);
for (int i = start; i <= end; i++) {
if (n % i != 0) continue;