22642: 括号生成

http://cs101.openjudge.cn/practice/22642/

Paul是一名数学专业的同学，在课余选修了C++编程课，现在他能够自己写程序判断判断一个给定的由'('和')'组成的字符串是否是正确匹配的。可是他不满足于此，想反其道而行之，设计一个程序，能够生成所有合法的括号组合，请你帮助他解决这个问题。

输入

输入只有一行N，代表生成括号的对数（1 ≤ N ≤ 10)。

输出

输出所有可能的并且有效的括号组合，按照字典序进行排列，每个组合占一行。

样例输入

样例输出

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

python

# 23n2300011072(蒋子轩)
def add(n, left, right, string):
    # 终止条件：如果已经放置了所有的括号
    if left == n and right == n:
        print(string)
        return

    # 如果我们仍然可以放置左括号，则添加左括号
    if left < n:
        add(n, left+1, right, string+'(')

    # 如果右括号数量小于左括号数量，则添加右括号
    if right < left:
        add(n, left, right+1, string+')')

n = int(input())
add(n, 0, 0, '')

22642: 括号生成 ​

22642: 括号生成