Problem statement

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

Solution

We can use dp technique here, where in dp[i][j] we keep all possible trees from numbers i ... j. We can also keep only one dimensional dp, but then we need to clone trees, adding the same values to all elements. However, number of trees is exponential, and I think it is not worth to make this optimization from O(n^2) to O(n) memory, because problem can be solved for only small n <= 50.

Complexity

Time and space complexity is O(C_{2n}^n) approximately, because we have Catalan number of trees.

Code

class Solution:
    def generateTrees(self, n):
        def dp(i, j):
            if i > j: return [None]
            ans = []
            
            for k in range(i, j + 1):
                for lft, rgh in product(dp(i, k-1), dp(k+1, j)):
                    root = ListNode(k)
                    root.left = lft
                    root.right = rgh
                    ans.append(root)            
            return ans
        
        return dp(1, n)