暴力--二进制
采用与：力扣---子集---回溯（子集型回溯）---递归-CSDN博客 中二进制求解一样的思路，即遍历0~
-1（从二进制去考虑），如果这个数的第 i 位为0，则括号的第 i 位为‘（ ’，为1代表‘ ）’。依次求出所有括号的可能性（总共
代码：
C++：
class Solution {
public:
bool check(string temp,int n){
stack<char> s;
int num=2*n;
for(int i=0;i<num;i++){
//先判断是否配对
if(temp[i]=='('){s.push(temp[i]);}
else{
if(s.empty()){return false;}
else{s.pop();}
}
}
if(s.empty()){return true;}
else{return false;}
}
vector<string> generateParenthesis(int n) {
vector<string> res;
int temp=2*n;
for(int i=0;i<(1<<temp);i++){ //0代表(，1代表)
string s;
for(int j=0;j<temp;j++){
if(i & (1<<j)){
s+=')';
}
else{s+='(';}
}
//cout<<s<<endl;
if(check(s,n)){res.push_back(s);}
}
return res;
}
};Python：
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
def check(temp:str,n:int) -> bool:
s=deque()
num=2*n
for i in range(num):
if temp[i]=='(':
s.append(temp[i])
else:
if len(s)==0:
return False
else:
s.pop()
if len(s)==0:
return True
else:
return False
res=[]
temp=2*n
temp_=1<<temp
for i in range(temp_):
s=""
for j in range(temp):
if i & (1<<j):
s+=')'
else:
s+='('
if check(s,n):
res.append(s)
return res注意：len(s)用于查看队列/栈中元素的个数，string在Python中的写法为str，Python中栈和队列都可以用deque来实现。deque：from collections import deque
暴力--回溯dfs
采用与：力扣---子集---回溯（子集型回溯）---递归-CSDN博客 中递归法一样的思路，分为三个步骤，第一步骤为特殊情况的判别，即
个位置已经填满，对其进行判别。第二步骤为第 i 为设置为‘(’，进行递归调用（注意保护现场）。第三步骤为第 i 为设置为‘ ）’，进行递归调用（注意保护现场）。
代码：
C++：
class Solution {
public:
bool check(string temp,int n){
stack<char> s;
int num=2*n;
for(int i=0;i<num;i++){
//先判断是否配对
if(temp[i]=='('){s.push(temp[i]);}
else{
if(s.empty()){return false;}
else{s.pop();}
}
}
if(s.empty()){return true;}
else{return false;}
}
void dfs(int i,vector<string>& res,string temp,int n){
if(i==2*n){
if(check(temp,n)){
res.push_back(temp);
}
return;
}
//将'('加入temp
temp+='(';
dfs(i+1,res,temp,n);
temp.pop_back();
//将')'加入temp
temp+=')';
dfs(i+1,res,temp,n);
temp.pop_back();
}
vector<string> generateParenthesis(int n) {
vector<string> res;
string temp;
dfs(0,res,temp,n);
return res;
}
};Python：
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
def check(temp:str,n:int) -> bool:
s=deque()
num=2*n
for i in range(num):
if temp[i]=='(':
s.append(temp[i])
else:
if len(s)==0:
return False
else:
s.pop()
if len(s)==0:
return True
else:
return False
def dfs(i:int,res:List[str],temp:str,n:int):
if i==2*n:
if check(temp,n):
res.append(temp)
return
temp+='('
dfs(i+1,res,temp,n)
temp=temp[0:len(temp)-1]
temp+=')'
dfs(i+1,res,temp,n)
temp=temp[0:len(temp)-1]
res=[]
temp=""
dfs(0,res,temp,n)
return res
对第二种写法的优化：
我们需要认识到一个点，遍历到第 i 位（即要确定第 i 位是左括号还是右括号时），前 i-1 位的左括号数量一定大于右括号的数量，第 i 位才可能是‘ ）’。所以我们可以在这部分进行改进：
//将')'加入temp temp+=')'; dfs(i+1,res,temp,n); temp.pop_back();同时，对特殊情况的判断也可以变为对左括号数量和对右括号数量的判断。
代码：
C++：
class Solution {
public:
//左括号数>右括号数，才能加右括号
void dfs(int i,vector<string>& res,string temp,int n,int left,int right){
if(i==2*n){
if(left==right){
res.push_back(temp);
}
return;
}
//将'('加入temp
temp+='(';
dfs(i+1,res,temp,n,left+1,right);
temp.pop_back();
//将')'加入temp
if(left>right){
temp+=')';
dfs(i+1,res,temp,n,left,right+1);
temp.pop_back();
}
}
vector<string> generateParenthesis(int n) {
vector<string> res;
string temp;
dfs(0,res,temp,n,0,0);
return res;
}
};Python：
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
def dfs(i:int,res:List[str],temp:str,n:int,left:int,right:int):
if i==2*n:
if left==right:
res.append(temp)
return
temp+='('
dfs(i+1,res,temp,n,left+1,right)
temp=temp[0:len(temp)-1]
if left>right:
temp+=')'
dfs(i+1,res,temp,n,left,right+1)
temp=temp[0:len(temp)-1]
res=[]
temp=""
dfs(0,res,temp,n,0,0)
return res
