【力扣LeetCode】22 括号生成

本文主要是介绍【力扣LeetCode】22 括号生成，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述（难度中）

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

链接

https://leetcode-cn.com/problems/generate-parentheses/

思路

显然用栈添加左括号，在某一时刻有三种情况，每种情况对应一种或两种操作
1、n为0且栈为空，结束，字符串构建完成
2、第一种情况，n为空，栈不为空，不可以再继续添加左括号，只能将栈中括号出栈，字符串添加右括号，这里栈中添加什么不重要，只是用于计数。其实换成一个整形变量用于计数即可，那样速度应该能快点。
3、第二种情况，n不为空，栈为空，字符串只能继续添加左括号，同时入栈。
4、第三种情况，n不为空，栈不为空，左括号和右括号分两种情况添加，两个递归路线。
这一题用递归遍历所有可能即可。

代码

class Solution {
public:vector<string> generateParenthesis(int n) {vector<string> ans;if(n == 0){return ans;}stack<char> s;string ss = "";recall(ans, ss, s, n);return ans;}void recall(vector<string>& ans, string ss, stack<char> s, int n){if(n == 0 && s.size() == 0){ans.push_back(ss);}else{if(n > 0 && s.size() == 0){ss += '(';s.push('(');recall(ans, ss, s, n-1);}else if(n == 0 && s.size() > 0){ss += ')';s.pop();recall(ans, ss, s, n);}else{string sss = ss + '(';s.push('(');recall(ans, sss, s, n-1);s.pop();sss = ss + ')';s.pop();recall(ans, sss, s, n);}}}
};

时间效率：
在这里插入图片描述
实在受不了leetcode平台给我的反馈，竟然只战胜11%的人，故将栈改为int型计数量，记录左括号比右括号多的个数。

class Solution {
public:vector<string> generateParenthesis(int n) {vector<string> ans;if(n == 0){return ans;}int s = 0;string ss = "";recall(ans, ss, s, n);return ans;}void recall(vector<string>& ans, string ss, int s, int n){if(n == 0 && s == 0){ans.push_back(ss);}else{if(n > 0 && s == 0){ss += '(';s++;recall(ans, ss, s, n-1);}else if(n == 0 && s > 0){ss += ')';s--;recall(ans, ss, s, n);}else{string sss = ss + '(';s++;recall(ans, sss, s, n-1);s--;sss = ss + ')';s--;recall(ans, sss, s, n);}}}
};