Python面试宝典第25题：括号生成

题目

        数字n代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且有效的括号组合。

        备注：1 <= n <= 8。

        示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

        示例 2：

输入：n = 1
输出：["()"]

递归法

        使用递归法求解此问题的基本思想是：将生成有效括号序列的问题分解为更小的子问题。对于每一对括号，我们都可以看作是在已有的有效括号序列基础上，或者在其前后分别添加一个左括号和右括号。为了保证序列的有效性，我们需要确保任何时候左括号的数量都不少于右括号的数量。因此，可以采用递归的方式，逐步构建所有可能的序列。使用递归法求解本题的主要步骤如下。

        1、定义递归函数。函数接受两个参数，left 表示还可以使用的左括号数量，right 表示还可以使用的右括号数量，以及当前已经构造的括号序列curr_str。

        2、递归终止条件。当left和right都