Python3 solution Fast With ExPlanation
Intuition\n Describe your first thoughts on how to solve this problem. \nWe can approach the problem by using a recursive approach. \n# Approach\n Describe your
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe can approach the problem by using a recursive approach. \n# Approach\n<!-- Describe your approach to solving the problem. -->\nTo solve this problem, we can use a recursive approach. We start from the first element of the array, and find the number of elements smaller and larger than the current node. We then make use of the combination formula to calculate the number of combinations with the current node. We then recursively call the same function for the left and right subarrays, and multiply the results together. Finally, we subtract one and take the modulo of the result with 10^9 + 7 to get our final answer. \n\n```\ndef comb(n, r):\n    return math.factorial(n) // (math.factorial(r) * math.factorial(n - r))\n```\n# Complexity\n- Time complexity:  $$O(n^2)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def numOfWays(self, nums: List[int]) -> int:\n        def dfs(nums):\n            if len(nums) <= 2: return 1\n            left = [n for n in nums if n < nums[0]]\n            right = [n for n in nums if n > nums[0]]\n            return comb(len(nums) - 1, len(left)) * dfs(left) * dfs(right)\n        return (dfs(nums) - 1) % (10 ** 9 + 7)\n```
['Array', 'Math', 'Divide and Conquer', 'Dynamic Programming', 'Python3']