#3852. 生成括号(C++三级)

生成括号(C++三级)

题目描述

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

内存限制:65536

输入

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

输出

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

样例输入

3

样例输出

((()))

(()())

(())()

()(())

()()()

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

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

Limitation

1s, 1024KiB for each test case.