1
class Solution {
2
 public:
3
  vector<TreeNode *> solve(int start, int end) {
4
    // base case
5
    if (start > end) {
6
      return {NULL};
7
    }
8
    vector<TreeNode *> lChild, rChild, res;
9
    // forming a tree, by keeping each node as root node
10
    for (int i = start; i <= end; i++) {
11
      // don't create node here, bcz for each combination of subtree, node with
12
      // new address has to be generated
13

14
      // recursive call for left,right child, they will return vector of all
15
      // possible subtrees
16
      lChild = solve(start, i - 1);
17
      rChild = solve(i + 1, end);
18

19
      // for each subtree returned by lChild, forming combination with each
20
      // subtree returned by rChild
21
      for (auto l : lChild) {
22
        for (auto r : rChild) {
23
          // generating new node for each combination
24
          TreeNode *node = new TreeNode(i);
25
          // attaching left, right childs
26
          node->left = l;
27
          node->right = r;
28
          res.push_back(node);
29
        }
30
      }
31
    }
32
    // returning all possible subtrees
33
    return res;
34
  }
35
  vector<TreeNode *> generateTrees(int n) {
36
    return solve(1, n);
37
  }
38
};