Approach Explained With Observation || Easy To Understand
Intuition\n\nDifferent permutation that yield same bst as given \n        OBSERVATION :- \n        [1] ROOT IS SAME \n        [2] NOW, COMES LEFT AND RIGHT PART
# Intuition\n```\nDifferent permutation that yield same bst as given \n        OBSERVATION :- \n        [1] ROOT IS SAME \n        [2] NOW, COMES LEFT AND RIGHT PART \n        [3] RELATIVE POSITION IS FIXED OF LEFT AND RIGHT PART\n        [4] COUNT NO OF PERMUTATION \n        [5] LEFT N-1 PLACE TO BE FILLED \n        [6] LET NO. OF ELEMENT IN RIGHT or LEFT BE X THAN n-1Cx -1  COMBINATION POSSIBLE\n            ALSO NEED TO TAKE IN COUNT LEFT AND RIGHT SUBTREE COMBINATION FURTHER\n        [7] -1 BECAUSE GIVEN BST ALSO COUNTED IN VALID \n        [8] EVERY SUBTREE CAN BE CONSIDERED INDIVIDUALLY AND COMBINATION FOR IT \n            CAN BE FOUND RECURSIVELY\n        [9] PRECOMPUTE COMBINATION LOGIC EFFECTIVELY USING PASCAL TRIANGLE LOGIC\n    \n```\n# Approach\n``` \nRECURSION + DP + MATHS\n```\n\n# Complexity\n- Time complexity:\n$$O(N^2)[RECURSION]+O(N^2) [PASCAL]$$ \n\n- Space complexity:\n$$O(N^2)$$ \n\n# Code\n```\nconst int mod = 1e9+7;\nclass Solution {\npublic:\n   void PascalTriangle(int n,vector<vector<int>>&dp){\n       for(int i=0;i<=n;i++){\n          dp[i] =  vector<int>(i+1,1); //initially all 1 \n          //Now Apply combination logic of adding prev_row and prev_col \n          for(int j=1;j<i;j++){\n              dp[i][j] = (dp[i-1][j-1] + dp[i-1][j])%mod;\n          }\n       }\n   }\n    int dfs(vector<int>&nums,vector<vector<int>>&dp){\n        vector<int>leftSubTree , rightSubTree ; \n         int n = nums.size() ; \n\n        //1 COMBINATION OF BST POSSIBLE\n        if(n<3)  return 1;\n\n        //FIND LEFT AND RIGHT SUBTREE FOR ROOT I.E nums[0] \n        for(int i=1;i<n;i++){\n            if(nums[i]>=nums[0]) rightSubTree.push_back(nums[i]);\n            if(nums[i]<nums[0]) leftSubTree.push_back(nums[i]);\n        } \n\n        int left = dfs(leftSubTree,dp)%mod ; \n        int right = dfs(rightSubTree,dp)%mod ; \n        int ele_atLeft = leftSubTree.size() ; \n\n        // n-1Cele_atLeft * left * right \n         return (1ll * (1ll * dp[n-1][ele_atLeft]*1ll * left)%mod * right)%mod ; \n    }\n    int numOfWays(vector<int>& nums) {\n        // Different permutation that yield same bst as given \n        //T.C -> O(N^2)[RECURSION]+O(N^2) [PASCAL]\n        //S.C -> O(N^2)[D.P]\n        int n = nums.size() ; \n        vector<vector<int>>dp(n+1) ; \n        PascalTriangle(n,dp);\n        int ways = dfs(nums,dp)-1; // -1 BECAUSE GIVEN BST ALSO COUNTED IN VALID \n        return ways;\n    }\n};\n```\n```\nIf you find this solutions to be helpful do upvote..It keeps me motivated :)\n```
['Math', 'Dynamic Programming', 'Recursion', 'Combinatorics', 'C++']