简答题 偏难
#7165

生成括号 Paul是一名数学专业的同学,在课余选修了C++编程课,现在他能够自己写程序判断判断一个给定的由'('和')'组成的字符串是否是正确匹配的。可是他不满…

生成括号

Paul是一名数学专业的同学,在课余选修了C++编程课,现在他能够自己写程序判断判断一个给定的由'('和')'组成的字符串是否是正确匹配的。可是他不满足于此,想反其道而行之,设计一个程序,能够生成所有合法的括号组合,请你帮助他解决这个问题。

时间限制:1000

内存限制:65536

输入

输入只有一行N,代表生成括号的对数(1 ≤ N ≤ 10)。

输出

输出所有可能的并且有效的括号组合,按照字典序进行排列,每个组合占一行。

样例输入

3

样例输出

((()))
(()())
(())()
()(())
()()()
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;bitset&gt; #include &lt;ctime&gt; #include &lt;iostream&gt; using namespace std; int N; bool judge(bitset&lt;20&gt; temp) {   int numL = 0, numR = 0; // numL 表0 左括号数 numR表1 右括号数   for (int i = 2 * N - 1; i &gt;= 0; i--) {     if (temp[i])       numR++;     else       numL++;     if (numL - numR &lt; 0)       return false; // 在任何一个位置所得的前缀中0的个数不少于1的个数。   }   if (numL != numR)     return false; // 有相同个数的0和1,都是N个   return true; } int main() {   cin &gt;&gt; N;   int max = 1 &lt;&lt; (2 * N - 1); // 2的2*N-1次方   // cout&lt;&lt;max&lt;&lt;endl;   for (int i = 1; i &lt;= max; i++) {     bitset&lt;20&gt; temp;     // 开始枚举每种可能     for (int j = 0; j &lt; 2 * N; j++) {       temp[j] = (i &gt;&gt; j) &amp; 1; // 这里是反着取的 如000111,先取个位的1     }     // 对每种可能进行判断     if (judge(temp)) {       for (int j = 2 * N - 1; j &gt;= 0; j--) {         if (temp[j])           cout &lt;&lt; ")"; // 所以这要反过来输出         else           cout &lt;&lt; "(";       }       cout &lt;&lt; endl;     }   }   return 0; }</pre>
这道题暂未补解析。