简答题
偏难
#7165
生成括号 Paul是一名数学专业的同学,在课余选修了C++编程课,现在他能够自己写程序判断判断一个给定的由'('和')'组成的字符串是否是正确匹配的。可是他不满…
生成括号
Paul是一名数学专业的同学,在课余选修了C++编程课,现在他能够自己写程序判断判断一个给定的由'('和')'组成的字符串是否是正确匹配的。可是他不满足于此,想反其道而行之,设计一个程序,能够生成所有合法的括号组合,请你帮助他解决这个问题。
时间限制:1000
内存限制:65536
输入
输入只有一行N,代表生成括号的对数(1 ≤ N ≤ 10)。
输出
输出所有可能的并且有效的括号组合,按照字典序进行排列,每个组合占一行。
样例输入
3
样例输出
((())) (()()) (())() ()(()) ()()()
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <bitset>
#include <ctime>
#include <iostream>
using namespace std;
int N;
bool judge(bitset<20> temp) {
int numL = 0, numR = 0; // numL 表0 左括号数 numR表1 右括号数
for (int i = 2 * N - 1; i >= 0; i--) {
if (temp[i])
numR++;
else
numL++;
if (numL - numR < 0)
return false; // 在任何一个位置所得的前缀中0的个数不少于1的个数。
}
if (numL != numR)
return false; // 有相同个数的0和1,都是N个
return true;
}
int main() {
cin >> N;
int max = 1 << (2 * N - 1); // 2的2*N-1次方
// cout<<max<<endl;
for (int i = 1; i <= max; i++) {
bitset<20> temp;
// 开始枚举每种可能
for (int j = 0; j < 2 * N; j++) {
temp[j] = (i >> j) & 1; // 这里是反着取的 如000111,先取个位的1
}
// 对每种可能进行判断
if (judge(temp)) {
for (int j = 2 * N - 1; j >= 0; j--) {
if (temp[j])
cout << ")"; // 所以这要反过来输出
else
cout << "(";
}
cout << endl;
}
}
return 0;
}</pre>
这道题暂未补解析。