C++ | Math | Combination Theory | Dynamic Programming
1569. Number of Ways to Reorder Array to Get Same BST\n\nIt\'s a interesting math problem. \n\nWe will solve this problem by recursion, it\'s a little similar t
**1569. Number of Ways to Reorder Array to Get Same BST**\n\nIt\'s a interesting math problem. \n\nWe will solve this problem by recursion, it\'s a little similar to dynamic programming.\n\n+ On the top level, there is no doubt that `nums[0]` is the root of BST.\n+ Remind that in BST, we have `left < root < right`.\n+ Thus, those numbers who are smaller than `nums[0]`, we put them in the vector `left` (which are the left children). And the others who greater than `nums[0]`, we put them in vector `right` (which are the right children).\n+ There are `n` position, index-0 is occupied by `nums[0]`. And we should put `left` in the remained `n-1` positions, there are `C[n-1][k]` cases, where `k` is the length of `left`.\n  > Remind the combination formula:\n  > `C[n][k] = C[n-1][k] + C[n-1][k-1]`\n\n+ Let `f(nums)` denote the number of cases, if we get the `left, right` vector mentioned above, then we can have:\n```cpp\nf(nums) = f(left) * f(right) * C[n - 1][k]\n```\nwhere `k` is the length of `left` vector, and `n` is the length of vector `nums`.\n\n```cpp\nclass Solution {\npublic:\n    const int mod = (int)(1e9) + 7;\n    vector<vector<int>> C;\n    int numOfWays(vector<int>& nums) \n    {\n        int n = nums.size();\n        C.resize(n, vector<int>(n, 0));\n        for (int i = 0; i < n; ++i)\n        {\n            C[i][0] = 1;\n            for (int j = 1; j <= i; ++j)\n                C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod;\n        }\n        return f(nums) % mod - 1;\n    }\n    \n    int64_t f(vector<int> &nums)\n    {\n        int n = nums.size();\n        if (n <= 1) return 1;\n        vector<int> left, right;\n        for (int i = 1; i < n; ++i)\n        {\n            if (nums[i] > nums[0]) right.emplace_back(nums[i]);\n            else left.emplace_back(nums[i]);\n        }\n        int64_t lval = f(left) % mod, rval = f(right) % mod;\n        return ((C[n - 1][left.size()] * lval) % mod * rval) % mod;\n    }\n};\n```\n\nThis solution is slow, but it can work :-D !\n
['Combinatorics']