每天一道算法：生成有效括号字符串

22、生成有效括号字符串

题目

给定整数n，要求输出 n 对左右括号的所有可能的有效组合。

示例：

思路

为了保证括号字符串是有效的，需要满足两个条件：

1、左括号必须有同样类型的右括号相匹配

2、右括号匹配顺序必须和左括号相对应

详情可以参考

每天一道算法：判断有效括号

。

可以使用递归法，来保证这两个条件，步骤如下：

1、起始有 n 个左括号和 n 个右括号需要拼接到字符串中。

2、先将结果字符串初始化为空。

3、每次递归时，选择其中一种括号，拼接到结果字符串的最右边。分为两种情况：

（1）如果剩余左括号和右括号的数量相等，那么下一步只能放左括号

（2）如果剩余右括号多于左括号，那么既可以放左括号，又可以放右括号

不可能出现左括号多于右括号的情况。

4、直至没有剩余括号为止。

比如：需要放两对括号，则

1、首先，只能放左括号，结果为'('

2、现在剩下 1 个左括号和 2 个右括号，因此两个都可以放，结果为 '()' 和 '(('

3、现在结果集有两种情况了，

（1）对于 '()'，还剩下各1种括号，因此只能放左括号，得到 '()('

（2）对于 '(('，还剩下2个右括号，因此既可以放左又可以放右，但是左括号剩余0个，因此只能放右括号，得到 '(()'

4、将最后一个剩余的字符拼接上去，得到 '()()' 和 '(())'

代码

python实现