Leecode22. 括号生成——Leecode大厂热题100道系列

电玩女神 2022-09-14 14:20 110阅读 0赞

## 我是小张同学，立志用最简洁的代码做最高效的表达 ##

--------------------

以下是我个人做的题解，每个题都尽量囊括了所有解法，并做到了最优解，欢迎大家收藏！留言！

## 传送门——>[**Leecode大厂热题100道系列题解**][Leecode_100] ##

--------------------

### 问题描述 ###

> 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。  
>   
> 有效括号组合需满足：左括号必须以正确的顺序闭合。

> 示例 1：  
> 输入：n = 3  
> 输出：\["((()))","(()())","(())()","()(())","()()()"\]  
>   
> 示例 2：  
> 输入：n = 1  
> 输出：\["()"\]

> 提示：  
> 1 <= n <= 8

--------------------

### 思路 ###

用dfs暴力搜索即可。 注意这里的dfs回溯参数可以不存在，一直以参数的形式呈现， 有点类似于递归。

--------------------

class Solution {
        
    public:
        vector<string>res;
        vector<string> generateParenthesis(int n) {
        
            dfs(n, 0, 0, "");
            return res;
        }
        void dfs(int n, int lc, int rc, string s) {
        
            if(lc == n && rc == n) {
        
                res.push_back(s);
                return;
            }
            if(lc < n) dfs(n, lc + 1, rc, s + "(");
            if(rc < n && rc < lc) dfs(n, lc, rc + 1, s + ")");
        }
    };

[Leecode_100]: https://zhanglong.blog.csdn.net/article/details/120545161