简答题
偏难
#7334
生成括号(2023.3) Paul是一名数学专业的同学,在课余选修了C++编程课,现在他能够自己写程序判断判断一个给定的由'('和')'组成的字符串是否是正确匹…
生成括号(2023.3)
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;
for (int i = 2 * N - 1; i >= 0; i--) {
if (temp[i])
numR++;
else
numL++;
if (numL - numR < 0)
return false;
}
if (numL != numR)
return false;
return true;
}
int main() {
cin >> N;
int max = 1 << (2 * N - 1);
for (int i = 1; i <= max; i++) {
bitset<20> temp;
for (int j = 0; j < 2 * N; j++) {
temp[j] = (i >> j) & 1;
}
if (judge(temp)) {
for (int j = 2 * N - 1; j >= 0; j--) {
if (temp[j])
cout << ")";
else
cout << "(";
}
cout << endl;
}
}
return 0;
}</pre>
这道题暂未补解析。