1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
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[]>();