# 95-Unique Binary Search Trees-II
###### tags: `Medium`
* Question:
https://leetcode.com/problems/unique-binary-search-trees-ii/
* Key:
1. 遇到這種凡舉的問題，最常想到的就是用遞迴(Recursion)去窮舉所有可能
2. Divid & conquer來窮舉所有的BST
3. 記得左右子樹要分開考量，所以要先固定左子樹或右子樹的情況下，來變化另一子樹的種類，達到窮舉的目的。
4. 思考窮舉如何優化

* Reference:
https://leetcode.com/problems/unique-binary-search-trees-ii/discuss/163316/C%2B%2B-Recursive-Solution(100)-with-explanation

* Hint:
1. 在每一次的遞迴裡面選定一個i作為root，然後將問題切成recursion(l, i-1)與recursion(i+1, r)
2. 同時設置終止條件當l > r則回傳NULL，這樣的時間複雜度就是O(2^n)。
3. 優化。優化這種recursion的方法通常就是memorization，也就是利用記憶體來記錄已經解過的recursion(l, r)
---> 用了一個二維的vector(l&r分別代表一個維度)，其element是每一個l&r所形成的tree set(vector<TreeNode*>)時間複雜度減少至O(n⁵)

class Solution {
public:
    vector<TreeNode*> gen(int start, int end){
        vector<TreeNode*> res;
        if(end<start){
            res.emplace_back(nullptr);
            return res;
        }
        if(end==start){
            res.emplace_back(new TreeNode(start));
            return res;
        }
        
        for(int i=start; i<=end;++i){
            vector<TreeNode*> left=gen(start, i-1);
            vector<TreeNode*> right = gen(i+1,end);
            for(int j=0; j<left.size();++j){
                for(int k=0; k<right.size();++k){
                    TreeNode *node = new TreeNode(i);
                    node->left=left[j];
                    node->right=right[k];
                    res.emplace_back(node);
                }
            }
        }
        return res;
    }
    vector<TreeNode*> generateTrees(int n) {
        if(n==0){
            return vector<TreeNode*>();
        }
        return gen(1,n);
    }
};