```class Solution {
public:
int numOfWays(vector<int>& nums) {
int m = nums.size();

table.resize( m + 1);
for(int i = 0; i < m + 1; ++i){
table[i] = vector<long long> (i+1, 1);
for(int j = 1; j < i ; ++j)
table[i][j] = (table[i-1][j-1] + table[i-1][j])%mod;
}
return (dfs(nums) - 1) % mod;
}
private:
vector<vector<long long>> table;
long long mod = 1e9+7;

long long dfs(vector<int>& nums){
int m = nums.size();
if( m  < 3)
return 1;
vector<int> leftNodes, rightNodes;
for(int i = 1; i < m ; i++){
if( nums[i] < nums)
leftNodes.push_back(nums[i]);
else
rightNodes.push_back(nums[i]);
}
long long leftWays = dfs(leftNodes) % mod;
long long rightWays = dfs(rightNodes) % mod;
return (((leftWays * rightWays) % mod) * table[m-1][leftNodes.size()])%mod;
}
};```
```    int uniquePaths(int m, int n) {
int N = m + n - 2, r = min(m, n)-1;
long long p = 1;
for(int i = 1 ; i <= r; i++){
p = (p *(N - i + 1))/i;
}
return p;
}```
star

Fri Jun 16 2023 07:57:40 GMT+0000 (Coordinated Universal Time) https://leetcode.com/problems/number-of-ways-to-reorder-array-to-get-same-bst/

#c++ #dfs #bst #dynamic_programming #combinatorics
star

Tue May 30 2023 14:27:01 GMT+0000 (Coordinated Universal Time) https://leetcode.com/problems/unique-paths/

#c++ #unique_paths #combinatorics

#### Save snippets that work with our extensions   