Editorial solution | C# | 100% efficient
Intuition\n Describe your first thoughts on how to solve this problem. \nFollowing the steps from the \'Editorial\' of the problem.\nhttps://leetcode.com/proble
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n*Following the steps from the \'Editorial\' of the problem.*\nhttps://leetcode.com/problems/number-of-ways-to-reorder-array-to-get-same-bst/editorial/\n\n***We can either implement a function to form Pascal Triangle..\n[or]\nDefine a function to calculate nCr -> n! / ((n-r)! * r!) with help of caching to avoid TLE due to same function being called over-and-over again during recursion***\n\n![Screenshot 2023-06-16 084304.png](https://assets.leetcode.com/users/images/31770ba5-575f-4213-9342-ca63d1a77e58_1686885266.3785398.png)\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(N ^ 2) - as we form Pascal Triangle\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(N ^ 2) - as we form Pascal Triangle\n\n# Code\n```\npublic class Solution {\n    Dictionary<long, double> cache = new Dictionary<long, double>();\n    int mod = 1000000007;\n    long[][] table;\n\n    public int NumOfWays(int[] nums) {\n        FormPascalTriagle(nums.Length);\n        return (int)DFS(nums.ToList()) - 1;\n    }\n\n    private long DFS(List<int> nums)\n    {\n        int n = nums.Count;\n        if (n <= 2)\n            return 1;\n        \n        List<int> smaller = new List<int>();\n        List<int> greater = new List<int>();\n\n        for (int i = 1; i < n; i++)\n        {\n            if (nums[i] < nums[0])\n                smaller.Add(nums[i]);\n            else\n                greater.Add(nums[i]);\n        }\n\n        //apply mod after every product to avoid overflow\n        return (table[n - 1][smaller.Count] * \n            (DFS(smaller) % mod) % mod) *\n            DFS(greater) % mod;\n\n    }\n\n    //Either form a Pascal triangle in the beginning..\n    //or\n    //implement a function to calculate nCr = n!/ ((n-r)! * r!)\n\n    //For the second approach, we\'ll have to have Cache in place...\n    //...to avoid TLE due to recursion calling same methods over and over again\n    private void FormPascalTriagle(int n) {\n        table = new long[n][];\n        for (int i = 0; i < n; i++)\n            table[i] = new long[n];\n\n        for (int i = 0; i < n; i++)\n        {\n            table[i][0] = 1;\n            table[i][i] = 1;\n        }\n\n        for (int i = 2; i < n; i++)\n        {\n            for (int j = 1; j < i; j++)\n            {\n                table[i][j] = (table[i - 1][j] + table[i - 1][j - 1]) % mod;\n            }\n        }\n    }\n}\n```
['Array', 'Math', 'Dynamic Programming', 'Binary Search Tree', 'C#']