C++ explanation for 1569
How does this work? Explaining it so that it might help some folks.\n\n\nCase I: Consider a BST: [4,2,1,3,5] \n         4                     [ level 0 ]\n    2
How does this work? Explaining it so that it might help some folks.\n\n```\nCase I: Consider a BST: [4,2,1,3,5] \n         4                     [ level 0 ]\n    2         5                [ level 1 ]\n 1     3 \nWe get these valid ways at level 0:\n  [4,2,1,3,5] \n  [4,2,1,5,3]\n  [4,2,5,1,3]\n  [4,5,2,1,3]\n  \n  [4,2,3,1,5]\n  [4,2,3,5,1]\n  [4,2,5,3,1]\n  [4,5,2,3,1]\n  \nThe root, 4, stays fixed.\n\nCase II: If we look at the left subtree, [2,1,3] at level 1:\n      2\n  1      3 \n... has the following valid ways:\n  [2,1,3]\n  [2,3,1]\n\nThe root, 2, stays fixed.\n\nCase III. Right subtree, [5] at level 1 has no children.\n     5\n... has the following valid ways:\n   [5]\n```\nClearly, Case I is dependent on case II and III.\n\nAt the crux of this problem is a fundamental math problem of merging two sequences to generate a number of new sequences where the order of the two sequences are not disturbed. This explains the problem: https://math.stackexchange.com/questions/666288/number-of-ways-to-interleave-two-ordered-sequences/ - the formula to use is *nCr* where n is the number of all elements in the two sequences and r is the number of elements in the first sequence.\n\n```\nMapping it to our problem (Case II), given the ordered sequences [1] and [3] how many ways to create a valid sequence \n(without disturbing the order of the first and second sequence):\n  [1, 3]\n  [3, 1]\n\nn = 2, r = 1, 2C1 = 2          <--- x (i.e n = number of left and right subtree nodes, r = number of left subtree nodes)\n\nIn Case III, there are no children.\nn = 0, r = 0, 0C0 = 1          <--- y (i.e n = number of left and right subtree nodes, r = number of left subtree nodes)\n\nMapping it to Case I, given the ordered sequences [2,1,3] and [5] how many ways to create a valid sequence \n(without disturbing the order of the first and second sequence):\n  [2,1,3,5] \n  [2,1,5,3]\n  [2,5,1,3]\n  [5,2,1,3]\n\nn = 4, r = 3. 4C3 = 4           <--- z (i.e n = number of left and right subtree nodes, r = number of left subtree nodes)\n\n... and given the ordered sequences [2,3,1] and [5]:\n  [2,3,1,5]\n  [2,3,5,1]\n  [2,5,3,1]\n  [5,2,3,1]\n\nn = 4, r = 3. 4C3 = 4\n```\nAs can be observed, the total number of valid sequences at any node can be derived by multiplying the sequences computed at itself and its children subtrees. At the root of the tree in Case I, this is simply x * y * z = 8. This is reflected in the recursion:\n```\n        return c * DFS(l) % M * DFS(r) % M;\n```\nThe code follows:\n```\nclass Solution {\npublic:\n    /*\n     * Formula for nCr = n! / r! * (n - r)!\n     * We will use Pascal\'s triangle\n     */\n    int M = 1000000007; /* calculations bounded by this */\n    long l[1001][1001] = { 0 }; bool init = false;\n\n    long combination(int n, int r) {\n        if (init/*ialized*/ == true) return l[n][r];\n        l[0][0] = 1;        /* We know 0C0 = 1, otherwise l[0] row is all 0s */\n        for (int i = 1; i < 1001; i++) {\n            l[i][0] = 1;    /* Set every nCr = 1 where r = 0 */\n            /* Set value for the current cell of Pascal\'s triangle i.e iC{1 ... i} */\n            for (int j = 1; j < i + 1; j++) {    \n                l[i][j] = (l[i - 1][j - 1] + l[i - 1][j]) % M; \n            } \n        }\n        init = true;\n        return l[n][r];\n    }\n\n    long DFS(vector<int>& nums)\n    {\n        if (nums.size() < 3) return 1; /* 1C1, 1C0, 0C0 */\n        vector<int> l, r;\n        /* Separate into left subtree sequence and right subtree sequence of nodes */\n        for (auto e : nums) { if (e > nums[0]) l.push_back(e); if (e < nums[0]) r.push_back(e); }\n        /* Use nCr formula for merging sequences */\n        long c = combination(l.size() + r.size(), l.size());\n        /* Recur down */\n        return c * DFS(l) % M * DFS(r) % M;\n    }\n    \n    int numOfWays(vector<int>& nums) {\n        return (int)DFS(nums) - 1 /* one sequence already given in nums */;\n    }\n};\n```\nPS: I initially wanted to use:\n```\n    /* Factorial */\n    long factorial(long n) { return (n == 1 || n == 0) ? 1 : (n * factorial(n - 1)); }\n    \n    long combination1(int n, int r) {\n        if (l[n][r]) return l[n][r];\n        /* Formula for nCr = n! / r! * (n - r)! */\n        l[n][r] = factorial(n) / (factorial(r) * factorial(n - r));    /* memoize */\n        return l[n][r];\n    }\n```\nThis works up to certain test cases and breaks because of no mod in it. Adding a mod in factorial() does not give the correct answer. So, it looks like this problem only works if the Pascal\'s triangle method is used and mod is done during addition and not at multiplication.
[]