[Python3] Divide and Conquer | detailed explanation
The idea is divide and conquer:\n1) To get the same BST,  we must first insert the root(the first element in the array), then we can insert its left subtree and
The idea is divide and conquer:\n1) To get the same BST,  we must first insert the root(the first element in the array), then we can insert its left subtree and right subtree.\n\n2) For both subtrees, we need to first insert root as well;\n\n3) when we have numbers of ways to arrange left subtree and right subtree, we only have to calculate the number of ways to arrange them into one array that does not change both subarrays\' original relative order within its elements.\n\nFor example, \n\n`nums = [3, 4, 5, 1, 2]`, `total_length` for both subtrees elements is `4`.\n\nFor left subtree, lnum = 1, only 1 arrangement: `[1, 2]`, `left_length = 2`\n\nFor right subtree, rnum = 1, only 1 arrangement: `[4, 5]`, `right_length = 2`\n\nThus, the total number of arrangements when put into one array should be equal to number of ways to take `left_length` positions out of `total_length`, which is `combinations(total_length, left_length)`. Here, we have `combinations(4, 2) = 6`, and the arrangements are:\n\n`[1,2,4,5]`\n\n`[1,4,2,5]`\n\n`[1,4,5,2]`\n\n`[4,1,2,5]`\n\n`[4,1,5,2]`\n\n`[4,5,1,2]`\n\nAlso, both subtrees could have more valid arragements, thus, the recurrence equation should be:\n\n`num(A) = num(left_subtree) * num(right_subtree) * combinations(total_length, left_length)`.\n\nFinally,  we need to `-1` because the input array should not be counted.\n\n```\nclass Solution:\n    def numOfWays(self, A: List[int]) -> int:\n        mod =10 ** 9 + 7\n        \n        def split(left, right):\n            lnum, rnum = 1, 1\n            if left:\n                lroot = left[0]\n                lnum = split([l for l in left if l < lroot], [r for r in left if r > lroot])\n            if right:\n                rroot = right[0]\n                rnum = split([l for l in right if l < rroot], [r for r in right if r > rroot])\n            return lnum * rnum * comb(len(left) + len(right), len(left))\n        \n        root = A[0]\n        return  split([l for l in A if l < root], [r for r in A if r > root]) % mod - 1\n```\n\nTime: `O(nlogn)`, similar to quick sort, each time we call `split`, we choose the the first element to be the pivot and split the input array to be two subarrays(one contains all the elements less than pivot, the other one contains all the elements larger than pivot).\nSpace: `O(nlogn)`.
[]