题目描述
如果字符序列仅由 ( 与 ) 构成，则在满足以下条件时，它是匹配的：
- 空序列是匹配的；
- 如果括号序列
s是匹配的，那么(s)也是匹配的； - 如果括号序列
s与t是匹配的，那么st也是匹配的。
给定一个整数 nn，请输出 nn 个左括号与 nn 个右括号可以组成的所有匹配括号序列，并且按照字典序将它们输出（如果超过 10001000 种，则仅输出前 10001000 种。）
输入格式
单个整数：表示 nn
输出格式
若干行：每行表示一种由 nn 对括号组成的匹配括号序列，按照字典序排列，如果超过 10001000 种，则仅输出前 10001000 种序列。
数据范围
- 1≤n≤501≤n≤50
样例数据
输入:
2
输出:
(())
()()
输入:
3
输出:
((()))
(()())
(())()
()(())
()()()
详见代码:
#include <bits/stdc++.h>
using namespace std;
int n;
char c[105];
int cnt=0;
void dfs(int step, int k)
{if (cnt>=1000) return;if (step > 2 * n){ for(int i = 1; i <= n * 2; i++) {cout<<c[i];}cout << endl;cnt++;return;}if (k + 1 <= 2 * n - step) {c[step] = '(';dfs(step + 1, k + 1);}if (k > 0) { c[step] = ')'; dfs(step + 1, k - 1); }return;
}
int main()
{cin >> n;dfs(1, 0);return 0;
}
