22. Generate Parentheses

Description

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example

For example, given n = 3, a solution set is:

1
2
3
4
5
6
7
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

Solution

最直接是递归然后剪枝,因为需要成对判断合法性,所以如果left > right的时候就可以剪掉了。
同时如果left == 0 的时候都可以直接把right的括号补全了。

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
/**
* @param {number} n
* @return {string[]}
*/
var generateParenthesis = function(n) {
if (n===0) return [];
if (n===1) return ['()'];

var result = [];
search(n,n,'',result);
return result;
};

function search(left,right,cur,result){
if (left < 0 || right < 0 || left > right)return;
if (left == 0){
for (let i = right; i > 0; i--){
cur += ')';
}
result.push(cur);
return;
}

search(left - 1, right, cur + '(', result);
search(left, right - 1, cur + ')', result);
}