LeetCode 22 括号生成(递归)

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例：

输入：n = 3
输出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]

思路

方法1：暴力

观察易得，符合括号序列和$n$的关系是，括号序列的个数有$2^{2n}$个，我们先把所有$2^{2n}$的括号全部打表打出来，然后再检验是否合法，最后输出合法的。

 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
class Solution
{
public:
    bool valid(string &str)
    {
        int balance = 0;
        for (char c : str)
        {
            if (c == '(')
                balance++;
            else
            {
                balance--;
                if (balance < 0)
                    return false;
            }
        }
        return balance == 0;
    }
    void generate_all(string &cur, int n, vector<string> &result)
    {
        if (n == cur.size())
        {
            if (valid(cur))
                result.push_back(cur);
            return;
        }
        cur += "(";
        generate_all(cur, n, result);
        cur.pop_back();
        cur += ")";
        generate_all(cur, n, result);
        cur.pop_back();
    }
    vector<string> generateParenthesis(int n)
    {
        vector<string> result;
        string cur = "";
        generate_all(cur, n * 2, result);
        return result;
    }
};

方法2：搜索

对方法1进行改进，可以只在括号序列有效时再添加 ( 或 ) ，而不是想方法一每次都添加，可以记录一下目前放置的所有括号的数量来做。

如果左括号数量小于$n$，那么就放置一个左括号，如果右括号的数量小于左括号的数量，就放一个右括号。

 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
class Solution
{
public:
    void generate(string &cur, int n, int open, int close, vector<string> &result)
    {
        if (cur.size() == n * 2)
        {
            result.push_back(cur);
            return;
        }
        if (open < n)
        {
            cur += "(";
            generate(cur, n, open + 1, close, result);
            cur.pop_back();
        }
        if (close < open)
        {
            cur += ")";
            generate(cur, n, open, close + 1, result);
            cur.pop_back();
        }
    }
    vector<string> generateParenthesis(int n)
    {
        vector<string> result;
        string cur;
        generate(cur, n, 0, 0, result);
        return result;
    }
};

最后修改于 2020-04-09

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。