3

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

1

()

def generate_parentheses(n: int):
    # 结果列表，用于存放所有有效的括号组合
    res = []
    
    def backtrack(s: str, left: int, right: int):
        # 如果左右括号都达到 n，则找到一个有效组合
        if left == n and right == n:
            res.append(s)
            return
        # 如果左括号数量小于 n，则可以添加左括号
        if left < n:
            backtrack(s + "(", left + 1, right)
        # 如果右括号数量小于左括号，则可以添加右括号
        if right < left:
            backtrack(s + ")", left, right + 1)
    
    # 从空字符串开始，左括号和右括号均为0
    backtrack("", 0, 0)
    return res

if __name__ == "__main__":
    n = int(input().strip())
    results = generate_parentheses(n)
    # 按要求每行输出一个结果
    for combination in results:
        print(combination)

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    // 主函数
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<String> result = generateParenthesis(n);
        // 每行输出一个有效组合
        for (String s : result) {
            System.out.println(s);
        }
        sc.close();
    }
    
    // 生成所有有效括号组合的函数
    public static List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        backtrack(res, "", 0, 0, n);
        return res;
    }
    
    // 回溯函数
    private static void backtrack(List<String> res, String s, int left, int right, int n) {
        // 当左右括号都达到 n 时，将当前组合加入结果列表
        if (left == n && right == n) {
            res.add(s);
            return;
        }
        // 如果左括号数量小于 n，则添加左括号
        if (left < n) {
            backtrack(res, s + "(", left + 1, right, n);
        }
        // 如果右括号数量小于左括号数量，则添加右括号
        if (right < left) {
            backtrack(res, s + ")", left, right + 1, n);
        }
    }
}

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// 回溯函数，用于生成所有有效括号组合
void backtrack(vector<string>& res, string s, int left, int right, int n) {
    // 如果左右括号数量均达到 n，说明得到一个有效组合
    if (left == n && right == n) {
        res.push_back(s);
        return;
    }
    // 如果左括号数量小于 n，则可以添加左括号
    if (left < n)
        backtrack(res, s + "(", left + 1, right, n);
    // 如果右括号数量小于左括号，则可以添加右括号
    if (right < left)
        backtrack(res, s + ")", left, right + 1, n);
}

int main() {
    int n;
    cin >> n;
    vector<string> res;
    // 从空字符串开始构造括号组合
    backtrack(res, "", 0, 0, n);
    // 每行输出一个有效括号组合
    for (const auto &s : res) {
        cout << s << endl;
    }
    return 0;
}