A49190. 生成括号Paul是一名数学专业的同学，在课余选修了C++编程课，现在他能够自己写程序判断判断一个给定的由'('和')'组成的字符串是否是正确匹配的。可是他不满足于此，想反其道而行之，设计一个程序，能够生成所有合法的括号组合，请你帮助他解决这个问题。输入输入只有一行N，代表生成括号的对数（1 ≤ N ≤ 10)。输出输出所有可能的并且有效的括号组合，按照字典序进行排列，每个组合占一行。样例输入3 …
填空题
中等
知识点
题目描述
生成括号
Paul是一名数学专业的同学，在课余选修了C++编程课，现在他能够自己写程序判断判断一个给定的由'('和')'组成的字符串是否是正确匹配的。可是他不满足于此，想反其道而行之，设计一个程序，能够生成所有合法的括号组合，请你帮助他解决这个问题。
输入
输入只有一行N，代表生成括号的对数（1 ≤ N ≤ 10)。
输出
输出所有可能的并且有效的括号组合，按照字典序进行排列，每个组合占一行。
样例输入
3
样例输出
((()))
(()())
(())()
()(())
()()()
参考答案
#include <iostream>
#include <bitset>
using namespace std;
int N;
bool judge(bitset<20>temp) {
int j = 0, num1 = 0;
while (j < 2*N) {
if (temp[j]) {
j++; num1++;
}
else {
j++; num1--;
}
if (num1 < 0) {
return false;
}
}
return true;
}
int main() {
cin >> N;
int max = 1 << (2*N - 1);//这里是2*N-1而不是2*N是因为1在最左边一定不成立，所以第一位一定是0，减少搜索量
for (int i = 1; i < max; i++) { //这里可以是i+=2，因为最后一位必须是1，不能是0，所以可以只考虑奇数
bitset<20> temp;
int cnt0 = 0, cnt1 = 0;
for (int j = 0; j < 2 * N; j++) {
temp[j] = (i >> j) & 1;
if (temp[j])
cnt1++;
else
cnt0++;
}
if (cnt1 != cnt0)
continue;
if (judge(temp)) {
for (int j = 0; j < 2 * N; j++) {
if (temp[2 * N - 1 - j])
cout << ")";
else cout << "(";
}
cout << endl;
}
}
return 0;
}答案解析
这道题比较简单，枚举然后验证就可以。
左括号对应0，右括号对应1，有效的括号组合就可以用01串来表示。看作2N位的01串。
从1到（2*N-1）枚举，有效的括号组合满足两个条件：
有相同个数的0和1，都是N个
以0开头，以1结尾，任何一个1前面有对应的0。也就是说，在任何一个位置所得的前缀中0的个数不少于1的个数。
上一题
下一题