leetcode 22. 括号生成

​
​

作者简介：C/C++ 、Golang 领域耕耘者，创作者
个人主页：作者主页
活动地址：CSDN21天学习挑战赛
题目来源： leetcode官网
如果感觉博主的文章还不错的话，还请关注➕ 、点赞👍 、收藏🧡三连支持一下博主哦~~~

💜 题目描述

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

示例1：

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

示例2：

输入：n = 1
输出：[“()”]

🧡 算法分析

此题方法是用dfs

与这一题类似，此类dfs题型作为经典题型

如果该题直接求数量，可以直接用拉特兰数公式的，

算法步骤:

1. 左右括号数量相等 （题目已经满足）
2. 任意前缀中 左括号数量 >= 右括号数量

怎么把所有方案列举出来呢

用递归处理，这题每位只有两种情况

• 左括号 : 任何情况都能填左括号（lc < n 左括号的数量小于n）
• 右括号 : 右括号需要有， 同时左括号的数量大于右括号（rc < n && lc > rc）

💚 代码实现

class Solution {
public:
    vector<string> re;

    // 如果只用求数量， 直接用卡特兰数公式即可
    vector<string> generateParenthesis(int n) {
        dfs(n, 0, 0, "");
        return re;
    }

    void dfs(int n, int lc, int rc, string path)
    {
        if(lc == n && rc == n) re.push_back(path);
        else
        {
            // 1. 左右括号数量相等
            // 2. 任意前缀中 左括号数量 >= 右括号数量   rc < n && lc > rc
            if(rc < n && lc > rc) dfs(n, lc , rc + 1, path + ')');
            if(lc < n) dfs(n, lc + 1, rc, path + '(');
        }
    }
    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

执行结果：

💙 时间复杂度分析

总时间复杂度为 O((1/n + 1 )*C(n, 2n))=O(C(n, 2n))。

如果觉得对你有帮助的话:
👍 点赞，你的认可是我创作的动力！
🧡 收藏，你的青睐是我努力的方向！
✏️ 评论，你的意见是我进步的财富！