[Java] Accepted Java solution
Didn\'t really enjoy the puzzle, started with long data type and kept MOD\'ing whenever I can but still overflow. I thought it was my algorithm but switching to
Didn\'t really enjoy the puzzle, started with long data type and kept MOD\'ing whenever I can but still overflow. I thought it was my algorithm but switching to BigInteger got it accepted.\n\nWell.. I guess it\'s simply not so java-friendly?\n\n**If LeetCode can hear me, I would really suggest we limit test cases below Long.MAX_VALUE. Going beyond that doesn\'t bring much meanful value IMO.**\n\n```\nimport java.math.BigInteger;\n\nclass Solution {\n    int MOD = 1000000007;\n    public int numOfWays(int[] nums) {\n        if(nums.length == 0) return 0;\n        List<Integer> list = new ArrayList<>();\n        for(int num : nums) list.add(num);\n        return (int)(helper(list).longValue() - 1);\n    }\n\n    private BigInteger helper(List<Integer> nums) {\n        if(nums.size() <= 2) return BigInteger.ONE;\n        int root = nums.get(0);\n        List<Integer> left = new ArrayList<>();\n        List<Integer> right = new ArrayList<>();\n        for(int i=1; i<nums.size(); i++) {\n            if(nums.get(i) < root) {\n                left.add(nums.get(i));\n            } else {\n                right.add(nums.get(i));\n            }\n        }\n        BigInteger count = combination(nums.size() - 1, left.size());\n        BigInteger leftCount = helper(left);\n        BigInteger rightCount = helper(right);\n        return count.multiply(leftCount).multiply(rightCount).mod(BigInteger.valueOf(MOD));\n    }\n\n    private BigInteger combination(int total, int num) {\n        num = Math.min(num, total - num);\n        if(num == 0) return BigInteger.ONE;\n\n        BigInteger res = BigInteger.ONE;\n        int limit = num;\n        long multi = total;\n        long did = 1;\n        for(int i=0; i<limit; i++) {\n            res = res.multiply(BigInteger.valueOf(multi--));\n            res = res.divide(BigInteger.valueOf(did++));\n        }\n\n        return res;\n    }\n}\n```
[]