[Python 3] Recursion, comb, beats 95+%
Intuition\nThe first idea I had here was that each root has to come before any of its children in the list, otherwise the tree will be out of order. This then m
# Intuition\nThe first idea I had here was that each root has to come before any of its children in the list, otherwise the tree will be out of order. This then made me think of splitting the problem into subtrees (recursion). For each tree, the total number of combinations possible is the number of ways to shuffle its child subtrees directly, then multiplied by the number of ways to shuffle each child subtree.\n\nFor more clarity, in the example `[3,4,5,1,2]`, we can obtain `[3,1,4,5,2]` by shuffling directly, and then we note that we cannot shuffle the individual subtrees `[4,5]` or `[1,2]` further.\n\n# Approach\nThe recursion is not too complex once we have the idea. The base case here is a tree with two or less nodes (only one way to order the elements). \n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nTime complexity is $$O(n^2)$$; each recursive layer requires an iteration through a linear array (pretty much.)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nSpace complexity is also $$O(n^2)$$.\n\n# Code\n```\nfrom math import comb\nclass Solution:\n    def numOfWays(self, nums: List[int]) -> int:\n        # each root must come before any of its children\n        # recursive call on each root given nodes in subtree\n        # for each tree - total number of nodes - 1 choose the number of nodes in one subtree\n        # multiply by the result for both subtrees\n\n        def recurse(nodes):\n            if len(nodes) <= 2:\n                return 1\n            else:\n                l = []\n                r = []\n                for val in nodes[1:]:\n                    if val > nodes[0]:\n                        r.append(val)\n                    else:\n                        l.append(val)\n                # comb calculates nCk\n                return comb(len(nodes) - 1, len(l)) * recurse(l) * recurse(r)\n\n        return (recurse(nums) - 1) % 1000000007\n```
['Recursion', 'Python3']