[C++], O(n^2) But easy to understand
Intuition\nThe problem asks us to find the number of ways to reorder an input array nums such that a binary search tree (BST) constructed from the reordered arr
# Intuition\nThe problem asks us to find the number of ways to reorder an input array nums such that a binary search tree (BST) constructed from the reordered array is identical to the BST formed from the original array. This problem can be solved by first understanding the properties of a BST, and then using dynamic programming to recursively count the number of ways to construct the BST.\n\n# Approach\nWe can start by observing that the root of the BST should always be the first element, let\'s call it `ref_val`. We can then partition the remaining elements of nums into two subarrays - one containing the elements smaller than the root, let\'s call it `x`, and the other containing the elements greater than the root, let\'s call it `y`. \n\nNow, for the BST construction to be valid, we can merge `x` and `y` in any order as long as we maintain the relative order within `x` and `y`. In other words, if we keep the relative order in `x` and `y`, however we choose to merge `x` and `y`, it is a valid answer. The number of ways to merge `x` and `y` can be calculated using the binomial coefficient (n choose k), where n is the total number of elements in x and y, and k is the number of elements in any of subarrays (since $$ncr(x+y,x) = ncr(x+y,y)$$). \nThis yields to: \n$$result = ncr(x.size()+y.size(), x.size())$$\nas the `result` would be a very large number, we utilize `nCrModp` to calculate a moded `ncr`. \n\n*BUT*, there is an issue in the solution, what if `x` or `y` could be reordered and again BST construction would be the same? We should multiply previously calculated `result` by number of possible reorders of `x` and `y` and this is done by recursively calling `numOfWays` on `x` and `y` to calculate `multiply_factor`\n\nNotice that we counted ALL possible ways including the one in the input, so we should subtract final result by one to get correct answer.\n\n# Complexity\n- Time complexity: $$O(n^2)$$\n\nThe time complexity of the solution is $$O(n^2)$$, where `n` is the length of the input array `nums`. This is because the `numOfWays` function recursively calls itself on the subarrays of `nums`, and the size of the subarrays being processed in each recursive call can be as large as `n`. In addition, the `nCrModp` function used to calculate the binomial coefficient has a time complexity of $$O(r)$$, where r is the size of the smaller subarray, which can also be as large as `n`.\n\n- Space complexity: $$O(n^2)$$\n\nThe space complexity of the solution is also $$O(n^2)$$, as the `nCrModp` function uses an array of size `r+1`, where `r` is the size of the smaller subarray, which can again be as large as `n`. In addition, the recursive calls to `numOfWays` create additional space for the call stack.\n# Code\n```\n#define ll long long\n#define MOD ((ll) (1e9+7))\n\nclass Solution {\npublic:\n    // https://www.geeksforgeeks.org/introduction-and-dynamic-programming-solution-to-compute-ncrp/\n    // Returns nCr % p\n    ll nCrModp(ll n, ll r, ll p)\n    {\n        // Optimization for the cases when r is large\n        if (r > n - r)\n            r = n - r;\n    \n        // The array C is going to store last row of\n        // pascal triangle at the end. And last entry\n        // of last row is nCr\n        ll C[r + 1];\n        memset(C, 0, sizeof(C));\n    \n        C[0] = 1; // Top row of Pascal Triangle\n    \n        // One by constructs remaining rows of Pascal\n        // Triangle from top to bottom\n        for (ll i = 1; i <= n; i++) {\n    \n            // Fill entries of current row using previous\n            // row values\n            for (ll j = min(i, r); j > 0; j--)\n    \n                // nCj = (n-1)Cj + (n-1)C(j-1);\n                C[j] = (C[j] + C[j - 1]) % p;\n        }\n        return C[r];\n    }\n  \n    int numOfWays(vector<int>& nums) {\n        if(nums.size() < 1 ) return 0;\n\n        int ref_val=nums[0];\n        vector<int> greater_than, smaller_than;\n\n        //dividing to smaller and bigger vector\n        for(auto &a:nums){\n            if(a<ref_val) smaller_than.push_back(a); \n            else if(a>ref_val) greater_than.push_back(a); \n        }\n\n        //FOR THE SAKE OF SIMPLICTY, EXTRA VARIABLES ARE CREATED\n\n        //counting how many ways we can reorder `smaller_than` and `greater_than` themselves \n        ll multiply_factor=1ll*(numOfWays(smaller_than)+1)*(numOfWays(greater_than)+1);\n        \n        //keeping moded value of `multiply_factor` as result\n        ll result = multiply_factor % MOD;\n\n        //counting how many ways we can merge `smaller_than` and `greater_than`, and multipling it by result \n        result*= nCrModp(smaller_than.size()+ greater_than.size(), smaller_than.size(), MOD);\n\n        //subtracting input from all possible values and return final result\n        return (result-1)%MOD;\n        \n    }\n};\n```
['Divide and Conquer', 'Dynamic Programming', 'Combinatorics', 'C++']