Luobuyu's Blog

0%

22.括号生成

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 850 阅读时长 ≈ 1 分钟
类似排列，枚举分支的个数，注意判断合法性。

22.括号生成

题目描述：

数字 $ n $ 代表需要生成括号的对数，设计函数，返回所有可能的并且有效的括号组合。

数据范围：
$ 1\le n \le 8 $

题解：

两个分支，一个加左括号，一个加右括号。注意判断合法性。使用一个总和 $ sum $ ，表示是否合法，遇到左括号加一，遇到右括号减一。最后如果 $ sum=0 $ 的话就是合法的。注意分支的个数限制，如果左括号的数量或者右括号的数量达到了 $ 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
32
33
34
35
36
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const static int INF = 0x3f3f3f3f;
    vector<string> ans;
    void dfs(int step, int& n, int suml, int sumr, string& cur, int sum)
    {
        if (sum < 0)
            return;
        if (step == n * 2 && sum == 0)
        {
            ans.emplace_back(cur);
            return;
        }
        if (suml < n)
        {
            cur.push_back('(');
            dfs(step + 1, n, suml + 1, sumr, cur, sum + 1);
            cur.pop_back();
        }
        if (sumr < n)
        {
            cur.push_back(')');
            dfs(step + 1, n, suml, sumr + 1, cur, sum - 1);
            cur.pop_back();
        }
    }
    vector<string> generateParenthesis(int n)
    {
        string cur;
        dfs(0, n, 0, 0, cur, 0);
        return ans;
    }
};