96. Unique Binary Trees

https://leetcode.com/problems/unique-binary-search-trees

Considering

Pickup i as the root node, then:

Left sub-tree: numTrees(i-1) Right sub-tree: numTrees(n-i)

And the possible permutations will be the product of left * right, which is

$$numTrees(n) = \sum_{i=1}^n numTrees(i-1) * numTrees(n-i)$$

Python

class Solution:
    def __init__(self):
        self.memory = {}

    def numTrees(self, n):
        if n in self.memory:
            return self.memory[n]
        if n in (0, 1):
            return 1

        ans = 0
        for i in range(1, n + 1):
            left = self.numTrees(i - 1)
            right = self.numTrees(n - i)
            ans += left * right

        self.memory[n] = ans
        return ans