1569. Number of Ways to Reorder Array to Get Same BST (Hard) - TengnanYao/daily_leetcode GitHub Wiki

class Solution(object):
    def numOfWays(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        def combine(n, x):
            res = 1
            for i in range(x + 1, n + 1):
                res *= i
            for i in range(n - x):
                res //= (i + 1)
            return res
        def count(arr):
            if len(arr) <= 2:
                return 1
            l, r = [], []
            for num in arr[1 : ]:
                if num < arr[0]:
                    l.append(num)
                else:
                    r.append(num)
            return combine(len(arr) - 1, len(l)) * count(l) * count(r)
        return (count(nums) - 1) % (10**9 + 7)