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

class Solution:
    def numOfWays(self, nums: List[int]) -> int:
        """
        main idea: with fixed root node, we can get list of left subtree and right subtree; we just need to keep both subtree's relative position in order 
                    - using Pasca; triangle 
        ==> note, given one sequence, we can get a tree but given one tree  we can generate multiple sequences.
        """
        M = 10**9+7
        n = len(nums)
        # build pascal triangle
        d = {}
        for i in range(n+1):
            d[i] = [1] * (i+1)
            for j in range(1,i):
                d[i][j] = (d[i-1][j-1]+d[i-1][j])%M
        def dfs(A):
            n = len(A)
            if n < 2:return 1
            # seperate left subtree and right subtree 
            left,right = [],[]
            for i in range(1,n):
                if A[i] < A[0]:
                    left.append(A[i])
                else:
                    right.append(A[i])
            # dfs left, right seperately 
            left_res = dfs(left)%M
            right_res = dfs(right)%M
            return (d[n-1][len(left)]*left_res) % M *right_res % M
        return dfs(nums)%M -1

class Solution:
    def numOfWays(self, nums: List[int]) -> int:
        """
        main idea: using interleave concept,  res = sequence of  left subtree L * sequence of right subtree * C(L+R,L) -1
                - as only as we decide the root node, left subtree and right subtree will be determined. All the rest we need to do is to count the left subtree sequence and right subtree sequence 
        """
        M = 10**9+7
        def ways_to_interleave(seq1:List[int],seq2:List[int]):
            total = len(seq1) + len(seq2)
            return math.comb(total,len(seq1)) 
        
        def dfs(subseq:List[int]):
            if not subseq:
                return 1
            root_val = subseq[0]
            left = [x for x in subseq if x < root_val]
            right = [x for x in subseq if x > root_val]
            ways_to_arrange_left = dfs(left)
            ways_to_arrange_right = dfs(right)
            return ways_to_arrange_left * ways_to_arrange_right * ways_to_interleave(left,right)
        return (dfs(nums)-1) % M