上海市计算机学会竞赛平台2022年7月月赛丙组匹配括号（三）

题目描述

如果字符序列仅由 ( 与 ) 构成，则在满足以下条件时，它是匹配的：

• 空序列是匹配的；
• 如果括号序列 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;
}