DP + COMBINATRICS + RECURSION (C++)
Trick to find nCr using dp is    nCr = n-1Cr-1 + n-1Cr\n\nlets suppose that we know the answer to rearrange the elements of left subtree and of the right subtre
**Trick to find nCr using dp is**    nCr = n-1Cr-1 + n-1Cr\n\nlets suppose that we know the answer to rearrange the elements of left subtree and of the right subtree and now we want to construct our final answer for current root\n\nout of ```n-1``` places we need to choose ```left.size( ) ``` places and put left subtree elements permutation on those places and right subtree elements in the remaining places.\n\n**so, ans = (n-1) C ( left.size( ) ) * left * right**\n\nleft is numbers of ways to rearrange the elements of left subree so that it generates the same bst as the left subtree of the original bst and similarly for the right.\nbasically left is the answer for our recursion call for left subtree and right is the answer for recursion call on right subtree.\n\n```\nclass Solution {\npublic:\n    \n    int mod = 1e9 + 7;\n    long long dp[1001][1001] = {};\n    \n    int helper(vector<int> & nums){\n        if(nums.size() <= 2)\n            return 1;\n        \n        int n = nums.size(); \n        vector<int> left, right;\n        for(int i = 1; i<n; i++){\n            if(nums[i] < nums[0])\n                left.push_back(nums[i]);\n            else right.push_back(nums[i]);\n        }\n        \n        int leftAns = helper(left), rightAns = helper(right);\n                \n        return (((dp[n-1][left.size()] * leftAns)%mod) * rightAns)%mod;\n    \n    }\n    \n    \n    int numOfWays(vector<int>& nums) {\n        for(int n = 0; n <= 1000; n++){\n            dp[n][0] = 1;\n        }\n        for(int n = 1; n <= 1000; n++){\n            for(int r = 1; r <= n; r++){\n\t\t\t\t// nCr = n-1Cr-1 + n-1Cr\n                dp[n][r] = (dp[n-1][r-1] + dp[n-1][r])%mod;\n            }\n        }\n        \n        int res = (helper(nums) - 1 + mod)%mod;\n        \n        return res;\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'C', 'Combinatorics']