⭐DP Recursion using Python 🔥Layman's Code 🔥⭐
An upvote would be appreciating...\n--\n# Intuition\nThe problem asks us to find the number of ways to reorder an array in order to obtain the same binary searc
**An upvote would be appreciating...**\n--\n# Intuition\nThe problem asks us to find the number of ways to reorder an array in order to obtain the same binary search tree (BST) structure. We can approach this problem by counting the number of valid BSTs that can be formed from the given array.\n\n# Approach\nTo solve this problem, we can use a recursive approach. We define a helper function `countBST` that takes an array of numbers as input and returns the count of valid BSTs that can be formed from that array. The base case occurs when the array has two or fewer elements, in which case there is only one valid BST.\n\nIn the recursive case, we choose the first element of the array as the root of the BST. We partition the remaining elements into two subarrays: one containing elements smaller than the root and the other containing elements greater than the root. We then recursively count the number of valid BSTs that can be formed from each subarray and multiply them together. Finally, we multiply this count by the number of combinations of choosing positions for the smaller and larger elements in the array.\n\nTo calculate the number of combinations, we define two helper functions: `fact` and `combs`. The `fact` function calculates the factorial of a given number modulo `10^9 + 7`. The `combs` function calculates the combination of choosing `r` elements from `n` elements using the factorial function and modular arithmetic.\n\nFinally, we subtract 1 from the total count of BSTs since we are not considering the original ordering of the array.\n\n# Complexity\n- Time complexity: O(n^2), where n is the number of elements in the input array. This is because for each recursive call, we partition the array into two subarrays, resulting in a total of n recursive calls.\n- Space complexity: O(n), where n is the number of elements in the input array. This is because we use recursion, which consumes memory on the call stack proportional to the depth of the recursion.\n\nHere is my code:\n```\nclass Solution:\n    def numOfWays(self, nums: List[int]) -> int:\n        m = (10**9) + 7\n\n        def fact(n):\n            r = 1\n            for i in range(1, n+1):\n                r = (r * i) % m\n            return r\n\n        def combs(n, r):\n            nr = fact(n)\n            dr = (fact(r) * fact(n - r)) % m\n            return (nr * pow(dr, m - 2, m)) % m\n\n        def countBST(nums):\n            if len(nums) <= 2:\n                return 1\n\n            left_nums = [n for n in nums if n < nums[0]]\n            right_nums = [n for n in nums if n > nums[0]]\n\n            left_count = countBST(left_nums)\n            right_count = countBST(right_nums)\n\n            return (combs(len(nums) - 1, len(left_nums)) * left_count * right_count) % m\n\n        return (countBST(nums) - 1) % m\n```
['Dynamic Programming', 'Binary Search Tree', 'Recursion', 'Binary Tree', 'Python3']