题目描述

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

内存限制：65536

输入

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

输出

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

样例输入

3

样例输出

((()))

(()())

(())()

()(())

()()()

解题思路： 本道题可以使用枚举法，把所有的可能性都列举出来，如果满足条件就把对应的结果输出 首先来说如何穷举每一种情况， 比如输入3，就是三对括号， 那么就有6个位置，每一种位置都有两种可能性， 所以一共就有2的6次方种可能性，

经过分析后发现第一位肯定是左括号， 所以只需要考虑后面5位减少到32种可能性， 对于每一种可能性只要满足两个条件就算是符合要求， 第一个就是左括号和右括号的数量相等， 第二个就是任意一个位置左括号的数量都是大于等于右括号的数量。

Limitation

1s, 1024KiB for each test case.