Java simple DFS
1, once root is fixed, find all following nums < root, list left, to form left subtree;\nfind all following nums >root, list right, to form left subtree;\n2, fi
1, once root is fixed, find all following nums < root, list<Integer> left, to form left subtree;\nfind all following nums >root, list<Integer> right, to form left subtree;\n2, find all combinations, comb, to select left.size() positions for left from all following positions after root, left.size() + right.size().\n3, result will be comb * dfs(left) * dfs(right);\n4, to calculate comb, you can either use [combination formula](https://www.mathplanet.com/education/algebra-2/discrete-mathematics-and-probability/permutations-and-combinations#:~:text=The%20number%20of%20combinations%20of,r!), or [Yang Hui Triangle](https://en.wikipedia.org/wiki/Yang_Hui) \n```\nclass Solution {\n    long mod = 1_000_000_007, dp[][];\n    public int numOfWays(int[] nums) {\n        dp = getYang(nums.length);\n        List<Integer> list = new ArrayList<>();      \n        for (int n : nums) list.add(n);\n        return (int) (dfs(list) - 1);\n    }\n    \n    private long dfs(List<Integer> l) {\n        if (l.size() < 3) return 1;\n        int root = l.get(0);\n        List<Integer> left = new ArrayList<>(), right = new ArrayList<>();\n        for (int i = 1; i < l.size(); i++) {\n            if (l.get(i) < root) left.add(l.get(i));\n            else right.add(l.get(i));\n        }\n        return dp[left.size() + right.size()][left.size()] % mod * dfs(left) % mod * dfs(right) % mod;\n    }\n    \n    private long[][] getYang(int n) {\n        long[][] res = new long[n + 1][n + 1];\n        for (int i = 1; i <= n; i++) res[i][0] = res[i][i] = 1;\n        for (int i = 2; i <= n; i++) \n            for (int j = 1; j < i; j++) \n                res[i][j] = (res[i - 1][j] + res[i - 1][j - 1]) % mod; \n        return res;\n    }\n}\n```
[]