[ C++ / Java ] ✅ Easy and Clean Code 🔥 Divide and Conquer 🔥 Beats 💯✅✅
Please Upvote if you like my Solution \uD83E\uDD17\uD83E\uDD17\n\n# Complexity \n- Time complexity: O(N^2) \n Add your time complexity here, e.g. O(n) \n\n- Spa
# Please Upvote if you like my Solution \uD83E\uDD17\uD83E\uDD17\n\n# Complexity \n- Time complexity: $$O(N^2)$$ \n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(N^2)$$ \n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n# C++ Code\n```\n#define ll long long\n\nclass Solution {\n    int mod = 1e9+7;\n    vector<vector<ll>> pascal;\n    \n    ll numOfWaysHelp(vector<int>& nums) {\n        if(nums.size() <= 2) return 1;\n\n        vector<int> leftSubtree, rightSubtree;\n        int n = nums.size();\n        for(int i=1; i<n; i++){\n            if( nums[i] < nums[0] ) leftSubtree.push_back(nums[i]);\n            else rightSubtree.push_back(nums[i]);\n        }\n\n        ll leftWays = numOfWaysHelp(leftSubtree), rightWays = numOfWaysHelp(rightSubtree);\n        int leftLen = leftSubtree.size(), rightLen = rightSubtree.size();\n        return (pascal[n-1][leftLen] * ((leftWays * rightWays)%mod))%mod;\n    }\npublic:\n    int numOfWays(vector<int>& nums) {\n        // calculate pascal triangle for calculating nCr in O(1)\n        int n = nums.size();\n        pascal.resize(n+1);\n        for(int i=0; i<n+1; i++){\n            pascal[i] = vector<ll>(i+1, 1);\n            for(int j=1; j<i; j++)\n                pascal[i][j] = (pascal[i-1][j-1] + pascal[i-1][j] )%mod;\n        }\n        \n        return numOfWaysHelp(nums)%mod - 1;\n    }\n};\n```\n\n---\n\n# Java Code\n```\nclass Solution {\n    int mod = (int)1e9+7;\n\n    private long numOfWaysHelp(List<Integer> nums, List<List<Integer>> pascal ) {\n        if(nums.size() <= 2) return 1;\n\n        List<Integer> leftSubtree = new ArrayList<>(), rightSubtree = new ArrayList<>();\n        int n = nums.size();\n        for(int i=1; i<n; i++){\n            if( nums.get(i) < nums.get(0) ) leftSubtree.add(nums.get(i));\n            else rightSubtree.add(nums.get(i));\n        }\n\n        long leftWays = numOfWaysHelp(leftSubtree, pascal), rightWays = numOfWaysHelp(rightSubtree, pascal);\n        int leftLen = leftSubtree.size(), rightLen = rightSubtree.size();\n        return (pascal.get(n-1).get(leftLen) * ((leftWays * rightWays)%mod))%mod;\n    }\n\n    public int numOfWays(int[] nums) {\n        // calculate pascal triangle for calculating nCr in O(1)\n        int n = nums.length;\n        List<List<Integer>> pascal = new ArrayList<>();\n\n        for(int i=0; i<n+1; i++){\n            Integer row[] = new Integer[i+1];\n            Arrays.fill(row, 1);\n            pascal.add(Arrays.asList(row));\n            for(int j=1; j<i; j++)\n                pascal.get(i).set(j, (pascal.get(i-1).get(j-1) + pascal.get(i-1).get(j) )%mod);\n        }\n\n        List<Integer> tmp = new ArrayList<>();\n        for(int x : nums) tmp.add(x);\n        return (int)numOfWaysHelp(tmp, pascal) - 1;\n    }\n}\n```\n\n![upvote-img.jpg](https://assets.leetcode.com/users/images/d20562b8-5ddb-40b3-8b8a-5d7a0a6f0b57_1684136359.2221565.jpeg)\n
['Divide and Conquer', 'Dynamic Programming', 'Tree', 'C++', 'Java']