#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
class Solution {
private:
vector<string> result;
string current;
void backtrack(int left, int right) {
// 左右括号都用完,得到一个合法组合
if(left == 0 && right == 0) {
result.push_back(current);
return;
}
// 剪枝:如果右括号剩余数量小于左括号,则不合法
if(left > right) return;
// 尝试添加左括号
if(left > 0) {
current.push_back('(');
backtrack(left - 1, right);
current.pop_back();
}
// 尝试添加右括号
if(right > 0) {
current.push_back(')');
backtrack(left, right - 1);
current.pop_back();
}
}
public:
vector<string> generateParenthesis(int n) {
backtrack(n, n);
sort(result.begin(), result.end());
return result;
}
};
int main() {
int n;
cin >> n;
Solution solution;
vector<string> ans = solution.generateParenthesis(n);
// 按要求格式输出
for(int i = 0; i < ans.size(); i++) {
cout << ans[i];
if(i < ans.size() - 1) cout << ",";
}
cout << endl;
return 0;
}
import java.util.*;
public class Main {
private List<String> result = new ArrayList<>();
private StringBuilder current = new StringBuilder();
private void backtrack(int left, int right) {
if(left == 0 && right == 0) {
result.add(current.toString());
return;
}
if(left > right) return;
if(left > 0) {
current.append('(');
backtrack(left - 1, right);
current.setLength(current.length() - 1);
}
if(right > 0) {
current.append(')');
backtrack(left, right - 1);
current.setLength(current.length() - 1);
}
}
public List<String> generateParenthesis(int n) {
backtrack(n, n);
Collections.sort(result);
return result;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Main solution = new Main();
List<String> ans = solution.generateParenthesis(n);
// 按要求格式输出
for(int i = 0; i < ans.size(); i++) {
System.out.print(ans.get(i));
if(i < ans.size() - 1) System.out.print(",");
}
System.out.println();
}
}
def generate_parenthesis(n):
result = []
def backtrack(left, right, current):
if left == 0 and right == 0:
result.append(current)
return
if left > right:
return
if left > 0:
backtrack(left - 1, right, current + '(')
if right > 0:
backtrack(left, right - 1, current + ')')
backtrack(n, n, '')
return sorted(result)
n = int(input())
ans = generate_parenthesis(n)
print(','.join(ans))