A22624. 括号
填空题
困难
知识点
题目描述
括号
题目描述
给定一个整数 n。生成所有长度为 n 的合法括号序列，并按字典序升序输出。合法括号序列定义：
（1）空字符串是合法的；
（2）若字符串 s 合法，则 (+s+) 合法；
（3）若字符串 s 和 t 合法，则 s+t 合法。
输入格式
输入一个整数 n。
输出格式
每行输出一个合法括号序列（按字典序升序）。若无解则不输出。
输入样例#1
2输出样例#1
()输入样例#2
4输出样例#2
(())
()()输入样例#3
6输出样例#3
((()))
(()())
(())()
()(())
()()()数据范围：
1≤N≤20，N 是偶数。
参考答案
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// 回溯函数：生成所有合法括号序列
// res：存储结果的向量
// path：当前构建的括号序列
// left：已使用的左括号数量
// right：已使用的右括号数量
// n：目标序列长度
void backtrack(vector<string>& res, string& path, int left, int right, int n) {
// 当当前序列长度达到n时，加入结果集
if (path.size() == n) {
res.push_back(path);
return;
}
// 优先添加左括号（保证字典序），左括号数量不超过n/2
if (left < n / 2) {
path.push_back('(');
backtrack(res, path, left + 1, right, n);
path.pop_back(); // 回溯，移除最后添加的左括号
}
// 再添加右括号，右括号数量不能超过左括号数量（保证合法性）
if (right < left) {
path.push_back(')');
backtrack(res, path, left, right + 1, n);
path.pop_back(); // 回溯，移除最后添加的右括号
}
}
int main() {
int n;
cin >> n;
vector<string> result;
string path;
backtrack(result, path, 0, 0, n);
// 输出所有合法序列
for (const string& s : result) {
cout << s << endl;
}
return 0;
}
上一题
下一题