The main and natural idea of this solution is to go through vertices and calculate number of combinations 'k' for each of them. k = kLeft * kRight.

Use cache to speed up recursion.

```
public class Solution {
private int[] cache = new int[100];
public int numTrees(int n) {
if(cache[n]>0){
return cache[n];
}
int k = 0;
for(int i = 1; i<= n; i++){
k+=Math.max(1,numTrees(i-1))*Math.max(1,numTrees(n-i));
}
cache[n]=k;
return k;
}
}
```