[Java] Clean code uses Yang Hui's/Pascal's Triangle With Explanation
This is actually a mathematical problem that can be solved by combination calculation, what\'d you do is basically arranging left and right sub-trees in correct
This is actually a mathematical problem that can be solved by combination calculation, what\'d you do is basically arranging left and right sub-trees in correct order but in all possible combinations.\nFor example for array ```[3,6,4,1]```\n```\n[3,6,4,1] left sub tree is [1], right tree is [6,4], \nwe just need to keep 6 appear in front of 4 to make permutation a valid one,\nso combinations can be [6,4,1], [6,1,4], [1,6,4]\nObviously, if left sub tree length is 1 and total length is 3, combination is 3C1 which is 3\n```\nExpand to a more complicated case ```[3,6,4,1,7]```\n```\nleft sub tree is [1], right tree is [6,4,7], \npermutations for right tree itself is [6,4,7], [6,7,4] which means it\'s 2C1 (combination of [4] and [7])\nfor every permuration of right tree you can also combine it with left tree [1] so total # is 4C1*2C1=8\n```\nTseudo code:\n```\ndef dfs(nums):\n\tif len(nums) <= 2:\n\t\treturn 1\n\tleft = [x in nums which < nums[0]]\n\tright = [x in nums which > nums[0]]\n\treturn combination(len(lefft+right), len(left)) * dfs(left) * dfs(right)\n```\nHere comes the tricky part for Java, doing mathematical stuff in Java is really a PAIN in the ass since it doesn\'t have ```comb()``` function in python and it doesn\'t support ```long long```, I didn\'t know why the hint is dynamic programming, now I get it, I can use Yang Hui/Pascal\'s triangle to speed up calculation and get rid of overflow, are you serious leetcode? \n```\nclass Solution {\n    private static final long MOD = 1000000007;\n    public int numOfWays(int[] nums) {\n        int len = nums.length;\n        List<Integer> arr = new ArrayList<>();\n        for (int n : nums) {\n            arr.add(n);\n        }\n        return (int)getCombs(arr, getTriangle(len + 1)) - 1;\n    }\n    \n    private long getCombs(List<Integer> nums, long[][] combs) {\n        if (nums.size() <= 2) {\n            return 1;\n        }\n        int root = nums.get(0);\n        List<Integer> left = new ArrayList<>();\n        List<Integer> right = new ArrayList<>();\n        for (int n : nums) {\n            if (n < root) {\n                left.add(n);\n            } else if (n > root) {\n                right.add(n);\n            }\n        }\n        // mod every number to avoid overflow\n        return (combs[left.size() + right.size()][left.size()] * (getCombs(left, combs) % MOD) % MOD) * getCombs(right, combs) % MOD;\n    }\n    \n    private long[][] getTriangle(int n) {\n        // Yang Hui (Pascle) triangle\n        // 4C2 = triangle[4][2] = 6\n        long[][] triangle = new long[n][n];\n        for (int i = 0; i < n; i++) {\n            triangle[i][0] = triangle[i][i] = 1;\n        }\n        for (int i = 2; i < n; i++) {\n            for (int j = 1; j < i; j++) {\n                triangle[i][j] = (triangle[i - 1][j] + triangle[i - 1][j - 1]) % MOD;\n            }\n        }\n        return triangle;\n    }\n}\n```
[]