[못풀었다/릿코드] 1569. Number of Ways to Reorder Array to Get Same BST

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

// Function return combination (Mathematics) [Formula = n!/( k!*(n-k)!)]
var nCr = (n,r) => {
    if(n < 2) return n;
    n = BigInt(n), r = BigInt(r);
    return fact(n) / (fact(n-r) * fact(r));
}

const cache = new Map(); // Chache for factorials
// Returns factorial of n [Formula = n!]
var fact = (n) => {
    if(n < 2) return 1n;
    if(cache.has(n)) return cache.get(n);
    const res = BigInt(n) * fact(n - 1n);
    cache.set(n, res);
    return res;
}

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

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

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

1.JS BigInt 공부하기

2.조합과 팩토리얼도 알아야한다.