Easy to understand code with nCr || C++ || Recursion || Fastest🔥
Approach\nAs mention in the problem we have to find the number of ways to reorder the given array which generates the same tree.\nThe first element can not be r
# Approach\nAs mention in the problem we have to find the number of ways to reorder the given array which generates the same tree.\nThe first element can not be rearranged because if we change its position the tree will change.\n\nThe dfs function is a recursive helper function that takes in the nums array and a 2D vector comb as input. It performs a depth-first search to calculate the number of different reorderings.\n\nThe base case for the recursion is when the size of the nums array is less than or equal to 2. In this case, there is only one way to reorder the elements, so the function returns 1.\n\nIf the size of the nums array is greater than 2, the function continues with the recursive approach. It splits the nums array into two parts: left and right. The left array contains all the elements smaller than the first element of nums, and the right array contains all the elements greater than the first element.\n\n# Complexity\n- Time complexity:\nO(n<sup>2</sup>)\ndfs(nums) recursively calls itself. In each call it find the number of elements greater than the first element which require O(n) time.\n Since the total call will be n. Thus the total time complexity of the recursive solution is O(n<sup>2</sup>)\n\n\n- Space complexity:\nO(n<sup>2</sup>)\nAs we vector of vector to store the combinations\n\n# If find usefull please upvote |\n\n# Code\n```\nclass Solution {\npublic:\n\n   int dfs(vector<int>& nums,vector<vector<int>>&comb) {\n            int n = nums.size(),md=1e9+7;\n            if (n <= 2) return 1;\n            vector<int> left, right;\n            for (int i = 1; i < n; ++i) {\n                if (nums[i] < nums[0]) left.push_back(nums[i]);\n                else right.push_back(nums[i]);\n            }\n            long long res = comb[n - 1][left.size()];\n            res = res * dfs(left,comb) % md;\n            res = res * dfs(right,comb) % md;\n            return (int)res;\n    }\n\n    int numOfWays(vector<int>& nums) {\n        int n = nums.size();\n        int md=1e9+7;\n        vector<vector<int>> comb(n + 1, vector<int>(n + 1));\n        comb[0][0] = 1;\n        for (int i = 1; i <= n; ++i) {\n            comb[i][0] = 1;\n            for (int j = 1; j <= i; ++j) {\n                comb[i][j]=(comb[i-1][j-1]+comb[i-1][j]) % md;\n            }\n        }\n        \n        return dfs(nums,comb) - 1;\n    }\n};\n```
['C++']