leetcode/algorithms/cpp/numberofWaystoReorderArraytoGetSameBST/numberofWaystoReorderArraytoGetSameBST.cpp at main · MichelleZ/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// Source: https://leetcode.com/problems/number-of-ways-to-reorder-array-to-get-same-bst/
// Author: Miao Zhang
// Date:   2021-05-16

class Solution {
public:
    int numOfWays(vector<int>& nums) {
        int n = nums.size();
        int kMod = 1e9 + 7;
        vector<vector<int>> cnk(n + 1, vector<int>(n + 1));
        for (int i = 0; i < n + 1; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0) cnk[i][j] = 1;
                else cnk[i][j] = (cnk[i - 1][j] + cnk[i - 1][j - 1]) % kMod;
            }
        }

        function<int(vector<int>)> trees = [&] (const vector<int>& nums) {
            int n = nums.size();
            if (n <= 2) return 1;
            vector<int> left;
            vector<int> right;
            for (int i = 1; i< nums.size(); i++) {
                if (nums[i] < nums[0]) left.push_back(nums[i]);
                else right.push_back(nums[i]);
            }
            long res = cnk[n - 1][left.size()];
            res = (res * trees(left)) % kMod;
            res = (res * trees(right)) % kMod;
            return static_cast<int>(res);
        };

        return trees(nums) - 1;
    }
};