Number of Ways to Reorder Array to Get Same BST LeetCode solution in JavaScript

1
// Main Function
2
var numOfWays = function (nums) {
3
  return (helper(nums) - 1n) % BigInt(1e9 + 7); // Return modulo value
4
};
5

6
// Function return combination (Mathematics) [Formula = n!/( k!*(n-k)!)]
7
var nCr = (n, r) => {
8
  if (n < 2) return 1n;
9
  (n = BigInt(n)), (r = BigInt(r));
10
  return fact(n) / (fact(n - r) * fact(r));
11
};
12

13
const cache = new Map(); // Chache for factorials
14
// Returns factorial of n [Formula = n!]
15
var fact = (n) => {
16
  if (n < 2) return 1n;
17
  if (cache.has(n)) return cache.get(n);
18
  const res = BigInt(n) * fact(n - 1n);
19
  cache.set(n, res);
20
  return res;
21
};
22

23
var helper = (nums) => {
24
  if (nums.length < 3) return 1n;
25

26
  const left = [],
27
    right = [];
28
  // Separate lower and higher values than first element in nums
29
  for (let i = 1; i < nums.length; ++i) {
30
    if (nums[i] < nums[0]) left.push(nums[i]);
31
    if (nums[i] > nums[0]) right.push(nums[i]);
32
  }
33

34
  // Number of possible combinations to get left and right separated
35
  const comb = nCr(nums.length - 1, left.length);
36
  return comb * helper(left) * helper(right);
37
};