# My DP solution with comments

• Start by constructing all possible trees with size 1. Then work your way up to next size in which step you combine previous calculated subtrees. In this DP solution bigger subproblems literally refer to smaller subproblems by pointing to them. That is multiple bigger trees might point to same smaller subtree.

``````class Solution {
// map (begin, end) to vector of TreeNode*
vector<vector<vector<TreeNode *>>> dp;
public:

vector<TreeNode*> generateTrees(int n) {
if (n == 0)
return {};

dp.resize(n+1);
for (auto &e : dp)
e.resize(n+1);

for (int size = 1; size <= n; size++) {
// pick start of range
for (int begin = 1; begin <= n - size + 1; begin++) {
int end = begin + size - 1;
// pick root in range
for (int r = begin; r <= end; r++) {
// all possible left and right subtrees
vector<TreeNode*> leftTrees, rightTrees;

if (r > begin)
leftTrees = dp[begin][r-1];
else
leftTrees.push_back(nullptr);
if (r < end)
rightTrees = dp[r+1][end];
else
rightTrees.push_back(nullptr);
// combine all possible left and right subtrees
for (auto leftTree : leftTrees)
for (auto rightTree : rightTrees) {
auto node = new TreeNode(r);
node->left = leftTree;
node->right = rightTree;
dp[begin][end].push_back(node);
}
}
}
}

return dp[1][n];
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.