[LeetCode]Generate Parentheses

首先很直观的做法，top-down的backtracking，我们根据当前剩余的左括号和右括号不断更新当前string然后递归直到用完所有括号，空间复杂度O(n)，n为括号总数，时间复杂度我们留到之后分析，代码如下：


另外一个解法是bottom up的recursion解法。假设我们有n组括号，当前有一个括号b，那么其所有排列的可能为:

1. 0组括号在b外面，n - 1组括号在b里面
2. 1组括号在b外面，n - 2组货号在b里面
3. ......
4. n - 1组括号在b外面，0组括号在b里面

在外面的括号我们不需要分b的左右，因为那样会导致重复。只需要决定一个方向即可，比如永远在b左边或者永远在b右边。举一个简单的例子，假设n为2，并且外面的括号永远在b左边，对应以上每个编号的可能，我们有:

• (())
• ()()

同理，假设n为3，我们有：

• ((()))
• (()())
• ()(())
• (())()
• ()()()

根据以上我们可以写出代码：

其中有很多重复的计算，我们可以用DP优化，代码如下：

时间复杂度分析

那么我们如何分析以上算法的时间复杂度呢，根据我们的分析，我们可以知道n组括号valid 排列的总数为Catalan Number，我们用C(n)表示第n个Catalan Number，那么C(n) = C(0)C(n - 1) + C(1)(n - 2) + ... + C(n - 1)C(0)。只要我们要generate所有的结果，那么时间复杂度一定是O(C(n))，DP可以免去一些不必要的计算但不会降低时间复杂度，因为结果数一定有这么多。