> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/leetcode/96.-unique-binary-search-trees.md).

# 96. Unique Binary Search Trees

## 1.問題

* 給一個n, 計算有多少BST組合

![](/files/-LK9sRaG5BrC4w8T3V6M)

## 2.想法

* When the number of nodes is 1 there is just one possible tree- this is the base case
* Consider that every node can be the root - the nodes before it will be on the left and the nodes after it on the right

## 3.程式碼

```
class Solution {
public:
    int numTrees(int n) {
        vector<int> v(n + 1, -1);
        return numTreesCount(n, v);
    }
private:
    int numTreesCount(int n, vector<int>& v) {
        if (n == 0 || n == 1) {
            return 1;
        }
        if (v[n] != -1) {
            return v[n]; 
        }
        
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            int left = numTreesCount(i - 1, v);
            int right = numTreesCount(n - i, v);
            sum = sum + left * right;
        }
        v[n] = sum;
        return sum;
    }
};
```

## 4.Performance

![](/files/-LK9xhB9-NvlJ-P1XFVq)