力扣：22-括号生成

题目描述

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

示例 1：

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

示例 2：

输入：n = 1
输出：["()"]
 

提示：

1 <= n <= 8

来源：力扣（LeetCode）

题目链接：力扣-22.括号生成

解题思路

就是判断左括号和右括号的数量，如果左括号和右括号的数量都为0说明这是一个有效的括号组合，如果左括号大于右括号说明不符合题意。因为可以发现，第一个字符一定是左括号，如果左括号大于右括号则说明前面有不匹配的括号，所以不符合题意。

因此，左括号一定是小于等于右括号的。当左括号小于等于右括号时，下一个字符可以是左括号也可以是右括号，都需要遍历一遍确保不会遗漏。

代码实现

class Solution {
vector<string>v;
public:
vector<string> generateParenthesis(int n) {
string s="";
recursion(s,n,n);//递归调用
return v;
}
void recursion(string s,int left,int right)
{
//如果左括号和右括号的数量都变为0
if(left==0&&right==0)
{
v.push_back(s);//加入到vector中
return;
}
//如果左括号大于右括号，不符合题意
if(left>right)
return;
//剩余左括号和右括号的数量相同，下一个用左括号
if(left==right)
recursion(s+"(",left-1,right);
else if(left<=right)//剩余左括号数量小于右括号的数量，下一个用左括号或者右括号都可以
{
//下一个用左括号
if(left>0)
recursion(s+"(",left-1,right);
//下一个用右括号
if(right>0)
recursion(s+")",left,right-1);
}
}
};

最后

以上就是拉长信封为你收集整理的力扣：22-括号生成的全部内容，希望文章能够帮你解决力扣：22-括号生成所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。