求教一路面试题：给定整数n，输出长度为n、只包括'{'和'}'且所有大括号按照c语法配对 的所有字符串
求教一道面试题：给定整数n，输出长度为n、只包括'{'和'}'、且所有大括号按照c语法配对 的所有字符串
再啰嗦一遍：给定整数n，输出所有满足以下条件的字符串
1. 长度为n
2. 只包括正反大括号，没有任何其他字符
3. 所有大括号能按照c语言的语法要求配对
举例，n=6的结果：
{{{}}}
{{}{}}
{{}}{}
{}{{}}
{}{}{}
不符合要求的几个例子(n=3或2)：
{}}
{{}
}{
我给出了一个作弊的答案：比如6吧，依次检查从0到63的所有整数的最低6位，把0当作'{'，1当作'}'，如果符合要求就输出。
判断是否符合要求的方法：int count=0;然后依次从左向右检查6位，如果是0就count++，如果是1就count--，如果任何时候count<0或者结束的时候count!=0就返回false。
对于比较大的n比如100，无法直接用整数表示位图的，如果还想用这个作弊方法，可能就得自己写个大型bitmap的类来实现。
我现在有几个问题：
1. 如果不用位图，直接用字符串，判断函数同样很容易写，但是怎么才能穷举所有的长度为n且只包括正反大括号的字符串？这个应该不太难，但是我还没想出来。
2. 不管用位图还是直接用字符串，先穷举再判断总不像是最高效的方法。能不能用什么办法直接只构造符合所有要求的字符串呢？
3. 应该也有递归解法，开始感觉很好写，但是我试着写了一下发现有些细节需要特别注意，还没写出来。
谢谢。
------解决方案--------------------
关注一下，期待答案
------解决方案--------------------
------解决方案--------------------
n为奇数时，无解。
再啰嗦一遍：给定整数n，输出所有满足以下条件的字符串
1. 长度为n
2. 只包括正反大括号，没有任何其他字符
3. 所有大括号能按照c语言的语法要求配对
举例，n=6的结果：
{{{}}}
{{}{}}
{{}}{}
{}{{}}
{}{}{}
不符合要求的几个例子(n=3或2)：
{}}
{{}
}{
我给出了一个作弊的答案：比如6吧，依次检查从0到63的所有整数的最低6位，把0当作'{'，1当作'}'，如果符合要求就输出。
判断是否符合要求的方法：int count=0;然后依次从左向右检查6位，如果是0就count++，如果是1就count--，如果任何时候count<0或者结束的时候count!=0就返回false。
对于比较大的n比如100，无法直接用整数表示位图的，如果还想用这个作弊方法，可能就得自己写个大型bitmap的类来实现。
我现在有几个问题：
1. 如果不用位图，直接用字符串，判断函数同样很容易写，但是怎么才能穷举所有的长度为n且只包括正反大括号的字符串？这个应该不太难，但是我还没想出来。
2. 不管用位图还是直接用字符串，先穷举再判断总不像是最高效的方法。能不能用什么办法直接只构造符合所有要求的字符串呢？
3. 应该也有递归解法，开始感觉很好写，但是我试着写了一下发现有些细节需要特别注意，还没写出来。
谢谢。
------解决方案--------------------
关注一下，期待答案
------解决方案--------------------
#include <set>
#include <string>
#include <iostream>
using namespace std;
set<string> res[20];
void solve(int n)
{
set<string> s;
res[1].insert("{}");
for(int i = 2 ; i <=n ; ++ i)
{
for(set<string>::iterator it = res[i - 1].begin() ; it != res[i - 1].end() ; ++ it)
{
res[i].insert(string("{}") + *it);
res[i].insert(*it + string("{}"));
res[i].insert(string("{") + *it + "}");
}
}
}
void print(int n)
{
for(set<string>::iterator it = res.begin() ; it != res.end() ; ++ it)
cout<<*it<<endl;
}
int main()
{
solve(6);
print(3);
}
------解决方案--------------------
n为奇数时，无解。