首页 › 题库 › C/C++编程考级 › C/C++编程六级 › 简答题
简答题 偏难
#13125

括号 给定一个整数 n。生成所有长度为 n 的合法括号序列,并按字典序升序输出。合法括号序列定义: (1)空字符串是合法的; (2)若字符串 s 合法,则 (+…

括号

给定一个整数 n。生成所有长度为 n 的合法括号序列,并按字典序升序输出。合法括号序列定义:

(1)空字符串是合法的;

(2)若字符串 s 合法,则 (+s+) 合法;

(3)若字符串 s 和 t 合法,则 s+t 合法。

时间限制:1000ms内存限制:256MB

输入格式

输入一个整数n。

输出格式

每行输出一个合法括号序列(按字典序升序)。若无解则不输出。


输入样例#1

2

输出样例#1

()

输入样例#2

4

输出样例#2

(())
()()

输入样例#3

6

输出样例#3

((()))
(()())
(())()
()(())
()()()

数据范围:

1≤N≤20,N 是偶数。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;string&gt; using namespace std; // 回溯函数:生成所有合法括号序列 // res:存储结果的向量 // path:当前构建的括号序列 // left:已使用的左括号数量 // right:已使用的右括号数量 // n:目标序列长度 void backtrack(vector&lt;string&gt;&amp; res, string&amp; path, int left, int right, int n) {     // 当当前序列长度达到n时,加入结果集     if (path.size() == n) {         res.push_back(path);         return;     }     // 优先添加左括号(保证字典序),左括号数量不超过n/2     if (left &lt; n / 2) {         path.push_back('(');         backtrack(res, path, left + 1, right, n);         path.pop_back(); // 回溯,移除最后添加的左括号     }     // 再添加右括号,右括号数量不能超过左括号数量(保证合法性)     if (right &lt; left) {         path.push_back(')');         backtrack(res, path, left, right + 1, n);         path.pop_back(); // 回溯,移除最后添加的右括号     } } int main() {     int n;     cin &gt;&gt; n;     vector&lt;string&gt; result;     string path;     backtrack(result, path, 0, 0, n);     // 输出所有合法序列     for (const string&amp; s : result) {         cout &lt;&lt; s &lt;&lt; endl;     }     return 0; }</pre>
这道题暂未补解析。