**Base Case**: a sequence of 1 element can generate just 1 Binary Search Tree

**Recursive Case**: for a sequence of `N`

elements we can take each of the elements `i`

as root. The number of possibles **BST** taking the element `i`

as root will be the number of combinations between all the possible **BST** generated from the elements on the left of the root, and all the possible **BST** generated from the elements on the right (the product).

We cache the results for a sequence of length `n`

to avoid computing multiple times the number of possible **BST** for the same length (**Dynamic Programming**).

Here is the code implementing this solution:

```
public static int numTrees(int n) {
int[] cache = new int[n+1];
cache[0]=cache[1]=1;
return nTrees(1,n,cache);
}
public static int nTrees(int left, int right,int[] cache) {
if(cache[right-left+1]>0) return cache[right-left+1];
for(int i=left;i<=right;i++) cache[right-left+1]+=nTrees(left,i-1,cache)*nTrees(i+1,right,cache);
return cache[right-left+1];
}
```