Leetcode 22.括号生成

题目描述：

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

示例 1：

1
2

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

示例 2：

1
2

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

提示：

• 1 <= n <= 8

链接：

https://leetcode-cn.com/problems/generate-parentheses

题目分析

  类似于 Leetcode 17.电话号码的字母组合，我们要获得所有的括号排列组合，则可以使用回溯的方法，维护一个字符串，每次加入一个左括号或者右括号，直到所有的括号添加完毕得到一个结果，再回溯删除，添加另外一种括号，如此穷举得到所有的结果。我们使用 n 来记录还未添加的左括号数目，使用 left 来记录还未匹配的左括号数目，则可以添加左括号的条件是 n > 0，可以添加右括号的条件是 left > 0，当 n == 0 && left == 0 时表明所有的括号已经添加并且匹配完毕，则得到一种结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    void backtrack(vector<string>& res, int n, int left, string& now){
        if(n == 0 && left == 0){
            res.push_back(now);
        }
        if(n > 0){
            now.push_back('(');
            backtrack(res, n-1, left+1, now);
            now.pop_back();
        }
        if(left > 0){
            now.push_back(')');
            backtrack(res, n, left-1, now);
            now.pop_back();
        }
    }
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        string now;
        backtrack(res, n, 0, now);
        return res;
    }
};

  时间复杂度：$O(\displaystyle\frac{4^n}{\sqrt{n}})$，其中 $n$ 是需要生成的括号对数目。这是由于 generateParenthesis(n) 的数目是第 $n$ 个卡特兰数 $\displaystyle\frac{1}{n+1}\begin{pmatrix}2n\\n\end{pmatrix}$，而这个数字由 $\displaystyle\frac{4^n}{n\sqrt{n}}$ 渐进界定。我们每得到一种结果，都需要耗费 $O(n)$ 的时间将其添加到答案数组中，因此总的时间复杂度为 $O(\displaystyle\frac{4^n}{n\sqrt{n}}\times n) = O(\displaystyle\frac{4^n}{\sqrt{n}})$。
  空间复杂度：$O(n)$，其中 $n$ 是需要生成的括号对数目。因为返回结果不计入空间开销，而其他开销主要取决于栈递归的层数，最大层数为 $2n$，每次递归调用的空间开销为 $O(1)$，因此空间复杂度为 $O(n)$。

  PS：相关阅读：卡特兰数-百度百科