Ruby solution with memoization and explanation (100%/100%)
Intuition\nUse recursion: for each tree, split it into the left subtree and the right subtree, then calculate the number of ways based on the length and structu
# Intuition\nUse recursion: for each tree, split it into the left subtree and the right subtree, then calculate the number of ways based on the length and structure of each subtree.\n\n# Approach\n0. Create a class memo to return the number of arrangements of normalized arrays.  (Normalized here means it uses the numbers 1-n.)\n\nFind the number of ways to form a tree from the original array with a helper function, subtract 1, and do modulo.\n\nMain helper function:\n1. Return a memoized version if it\'s stored.\n\n2. Divide the elements other than the root into the left subtree and right subtree, keeping them in the same order.\n3. Normalize the right subtree (e.g., if it\'s [5,7,6], convert it to [1,3,2]).  We do this with a helper function.  (Note that we don\'t have to normalize the left; since it\'s the smaller section of a normalized array, it will always go 1-n.)\n4. Find the number of ways to arrange each subtree.\n\n5. Multiply the number of ways to arrange each subtree for result.\n6. Multiply this result by the orderings helper function.\n\nAs an example, if the left subtree had 3 elements and the right subtree had 5 elements, they would have 8 elements in total.  The left elements have to keep relative order, as do the right elements, but we can changes when we do left elements versus right elements.  Essentially, we have 8 spots and want to find how many ways we can choose 3 of them to be elements from the left subtree.  This is just combinations, which we can calculate with factorials.  (Look up combinations/factorials if this part doesn\'t make sense.)\n\n7. Mod the result, memoize, and return.\n\n# Complexity\n- Time complexity:\nThis is pretty from quick sort, but it divides the array the same way in the recursive step, so time complexity is the same: $$O(n *log(n))$$ average case, $$O(n^2)$$ worst case.\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\n@memo = {[] => 1, [1] => 1, [1,2] => 1}\n\ndef num_of_ways(nums)\n    (num_ways(nums) - 1) % 1000000007\nend\n\ndef num_ways(nums)\n    return @memo[nums] if @memo[nums]\n\n    left = nums.select { |num| num < nums[0] }\n    right = nums.select { |num| num > nums[0] }\n    right = normalize(right)\n    left_ways,right_ways = num_ways(left),num_ways(right)\n\n    res = left_ways * right_ways\n    res *= orderings(left.length,right.length)\n\n    @memo[nums] = res % 1000000007\nend\n\ndef orderings(a,b)\n    fact(a+b) / fact(a) / fact(b)\nend\n\ndef fact(n)\n    return 1 if n < 2\n    i = 1\n    (2..n).each { |k| i *= k }\n    i\nend\n```
['Ruby']