5ef18f160aac5b27f31b22f28f584829
(难度Medium)Problem 22. Generate Parentheses(生成括号)

链接

https://leetcode.com/problems/generate-parentheses/solution/

难度等级

Medium

题干

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

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

[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

题意

给定一个n,要求返回n对括号所有合法组合。

样例

3

[
"((()))",
"(()())",
"(())()",
"()(())", 
"()()()"
]

题解

解法一: 暴力

暴力的解法应该最容易想到,因为n是确定的,也就是说一共有n个左括号和n个右括号。很容易想到,我们可以对这2n个字符进行排列组合,之后再对所有的组合进行过滤。留下合法的且不重复的即可。

伪代码很容易写:

# l表示当前已使用的左括号的数量,r表示已使用的右括号的数量
dfs brute_force(str, l, r):
    if l == n and r == n:
        ans.append(str)
    if l < n:
        brute_force(str+'(', l+1, r)
    if r < n:
        brute_force(str+')', l, r+1)

写完了再根据结果判断是否合法,留下合法的所有情况即可。

这样编码的确不难,而且也很容易想到,但是计算n个字符的排列组合复杂度是$O(2^n)$是一个指数级的算法,复杂度是我们不能接受的。而且根据上一题当中的结论,在匹配括号的时候是可以取巧的,我们其实没必要把所有的情况都枚举到。因为想要括号匹配合法,必须有一条,对于字符串当中的任何一个位置i,都必须有:$\sum_{j=1}^i {'('} {>=} \sum_{j=1}^i {')'}$,否则就是非法的。

也就是说必须要保证任意一个位置右括号的数量小于等于左括号的数量,不然的话,多余的右括号永远也无法匹配。

利用这点,就有了我们第二个方法:回溯法。

解法二: 回溯

既然左括号的数量必须大于右括号的数量,我们完全可以据此进行优化。我们在递归的时候对l和r进行大小判断,保证所有时刻都有l >= r即可。

伪代码如下:

dfs brute_force(str, l, r):
    if l == n and r == n:
        ans.append(str)
    if l < n:
        brute_force(str+'(', l+1, r)
    if r < l:
        brute_force(str+')', l, r+1)

提交代码:

```
class Solution {
public:

void dfs(int n, int l, int r, string str, vector<string>& vt) {
    if (l+r == 2 *n) {
top Created with Sketch.