EASY WELL EXPLAINED DP || COMBINATION SOLUTION
Intuition\n Describe your first thoughts on how to solve this problem. \nThe intuition behind the solution is to recursively divide the array into two parts, a 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe intuition behind the solution is to recursively divide the array into two parts, a left part and a right part. The left part contains numbers smaller than the first element of the array,i.e root of the tree, and the right part contains numbers greater than or equal to the first element. The number of ways to split the array can be calculated by multiplying the number of ways to split the left part and the right part with the total number of combinations possible for the remaining elements.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe numOfWays function takes an input array nums and returns the number of ways to split the array as described above.\nIt initializes a variable mod with the value 1e9 + 7, which will be used for modular arithmetic.\nIt creates a 2D vector dp of size (n + 1) x (n + 1), where n is the size of the input array. This vector will be used to store precomputed values of binomial coefficients.\nIt then calls a helper function sol with the input array nums and the dp vector.\nInside the sol function, if the size of the input array is less than or equal to 2, it returns 1 since there is only one way to split such arrays.\nOtherwise, it initializes two vectors left and right to store the numbers that are smaller and greater than or equal to the first element of the array, respectively.\nIt recursively calculates the number of ways to split the left and right parts by calling sol with the respective vectors.\nFinally, it returns the result by multiplying the number of ways to split the left and right parts with the binomial coefficient calculated using the dp vector. It uses modular arithmetic to avoid integer overflow.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe code initializes the dp vector with binomial coefficients in O(n^2) time, where n is the size of the input array.\nThe sol function is called recursively, and at each recursion level, it splits the array into two parts, which takes O(n) time.\nOverall, the time complexity of the code is O(n^3) because the sol function is called recursively for each element in the array, and calculating binomial coefficients takes O(n^2) time.\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe code uses a 2D vector dp of size (n + 1) x (n + 1), which requires O(n^2) space.\nThe recursion depth of the sol function is at most n, so the space complexity of the recursion stack is O(n).\nOverall, the space complexity of the code is O(n^2) due to the dp vector.dp\n# Code\n```\nclass Solution {\npublic:\nlong long mod=1e9+7;\nint sol(vector<int>&num,vector<vector<long long>> &dp){\n    int n=num.size();\n    if(n<=2) return 1;\n     vector<int> left,right;\n       for(int i=1;i<n;i++){\n       if(num[i]<num[0]) left.push_back(num[i]);\n       else right.push_back(num[i]);\n       }\n       return (((dp[n-1][left.size()]*(sol(left,dp)))%mod)*(sol(right,dp)))%mod;//nCr-->dp\n}\n    int numOfWays(vector<int>& nums) {\n        int n=nums.size();\n         vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, 0));\n        for (int i=0;i<=n;i++){\n            dp[i][0]=1;\n            dp[i][i]=1;\n            for (int j=1;j<i;j++)\n               dp[i][j]=(dp[i-1][j-1] + dp[i-1][j])%mod;\n        }\n        return sol(nums,dp)-1;\n    }\n};\n```
['Dynamic Programming', 'Tree', 'Binary Search Tree', 'Combinatorics', 'C++']