leetcode-22. 括号生成

本文最后更新于：2022年8月31日 晚上

leetcode-22. 括号生成

ACM模式

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
#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

/*
dfs:
一个合法的括号序列：
1、任意前缀中，左括号的数量 一定 >= 右括号的数量
2、左右括号数量相等 n == n

_ _ _ _
什么情况下可以填左括号：lcnt < n 就可以填
什么情况下可以填右括号：rcnt < n &&  左括号数量严格大于右括号数量lcnt > rcnt，
才能填
*/

int n;
vector<string> res;

// 括号的对数n，左括号个数lcnt，右括号个数rcnt，str括号序列
void dfs(int n, int lcnt, int rcnt, string str)
{
    // 终止条件
    // if (u == 2*n)
    if (lcnt == n && rcnt == n)
        res.push_back(str);
    else {
        if (lcnt < n)
            dfs(n, lcnt+1, rcnt, str+'(');

        if (rcnt < n && lcnt > rcnt)
            dfs(n, lcnt, rcnt+1, str+')');
    }
}

int main()
{

    cin >> n;

    dfs(n, 0, 0, "");
    for (auto x : res) cout << x << endl;
    return 0;
}

核心代码模式

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
class Solution {
public:
    vector<string> res;

    void dfs(int n, int lcnt, int rcnt, string str)
    {
        if (lcnt == n && rcnt == n)
        {
            res.push_back(str);
        }
        else {
            if (lcnt < n)
                dfs(n, lcnt + 1, rcnt, str + '(');
            
            if (rcnt < n && lcnt > rcnt)
                dfs(n, lcnt, rcnt + 1, str + ')');
        }
    }

    vector<string> generateParenthesis(int n) {
        
        dfs(n, 0, 0, "");
        return res;
    }
};
leetcode
leetcode

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！