BinarySearch 0910 Permutations to Generate Binary Search Tree

Problem statement

https://binarysearch.com/problems/Permutations-to-Generate-Binary-Search-Tree/

Solution

Equal to Leetcode 1569. Number of Ways to Reorder Array to Get Same BST.

Complexity

Time complexity is O(n^2), space is potentially also O(n^2).

Code

class Solution:
    def solve(self, nums):
        def dfs(A):
            if not A: return 1
            lft = [i for i in A[1:] if i > A[0]]
            rgh = [i for i in A[1:] if i < A[0]]
            return dfs(lft) * dfs(rgh) * comb(len(A) - 1, len(lft)) % (10**9 + 7)

        return dfs(nums) - 1