class Solution {
public:
map<string,int> hash={{"(",1},{")",-1}};
bool canaddRight(string str){
int i=0;
string s;
int j;
for(j=0;j<str.size();j++){
s=str.substr(j,1);
i+=hash[s];
}
return i;
}
int count(string str){
int i=0;
string s;
int j;
for(j=0;j<str.size();j++){
s=str.substr(j,1);
i+=hash[s]==1?1:0;
}
return i;
}
vector<string> generateParenthesis(int n) {
vector<string> ans;
queue<string> p;
if(n==0){
return ans;
}
p.push("(");
string s,s_;
while(!p.empty()){
s=p.front();
if(s.size()==2*n-1){
ans.push_back(s+")");
}
else{
if(canaddRight(s)){
p.push(s+")");
}
if(count(s)<n){
p.push(s+"(");
}
}
p.pop();
}
return ans;
}
};
这道题基本上就是两种思路，遍历或者动态规划（状态转移），遍历是用时间换空间，遍历是用空间换时间（存储所有n小的状态来减少遍历）。
