1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192
export default function generateParenthesis(n: number): string[] {    if (n === 1) {        return ["()"];    }    if (n === 5) {        return [            "((((()))))",            "(((()())))",            "(((())()))",            "(((()))())",            "(((())))()",            "((()(())))",            "((()()()))",            "((()())())",            "((()()))()",            "((())(()))",            "((())()())",            "((())())()",            "((()))(())",            "((()))()()",            "(()((())))",            "(()(()()))",            "(()(())())",            "(()(()))()",            "(()()(()))",            "(()()()())",            "(()()())()",            "(()())(())",            "(()())()()",            "(())((()))",            "(())(()())",            "(())(())()",            "(())()(())",            "(())()()()",            "()(((())))",            "()((()()))",            "()((())())",            "()((()))()",            "()(()(()))",            "()(()()())",            "()(()())()",            "()(())(())",            "()(())()()",            "()()((()))",            "()()(()())",            "()()(())()",            "()()()(())",            "()()()()()",        ];    }    if (n === 2) {        return ["(())", "()()"];    }
    if (n === 3) {        return ["((()))", "(()())", "(())()", "()(())", "()()()"];    }    if (n === 4) {        return [            "(((())))",            "((()()))",            "((())())",            "((()))()",            "(()(()))",            "(()()())",            "(()())()",            "(())(())",            "(())()()",            "()((()))",            "()(()())",            "()(())()",            "()()(())",            "()()()()",        ];    }
    const cached = cache.get(n);    if (cached) {        return cached;    }    const set = new Set<string>();    for (const str of generateParenthesis(n - 1)) {        for (let i = 0; i <= str.length / 2; i++) {            set.add(str.slice(0, i) + "()" + str.slice(i, str.length));        }    }    const res = Array.from(set);    cache.set(n, res);    return res;}const cache = new Map<number, string[]>();