22. Generate Parentheses

▶ 问题：给定正整数 n，求由 n 对小括号组成的所有合法表达式，显然所求表达式的个数为卡塔兰数 C(2n,n) / (n+1) 。

● 暴力枚举，超时。回溯法添加字符，添加够了以后进行检查，时间复杂度 O(2²ⁿ)。

 1 class Solution
 2 {
 3 public:
 4     vector<string> output;
 5 
 6     inline bool valid(string input)
 7     {
 8         int i, count;
 9         for (i = count = 0; i < input.size(); i++)
10         {
11             (input[i] == '(') ? count++ : count--;
12             if (count < 0)
13                 return false;
14         }
15         return (count == 0);
16     }
17     void generate(string current, int pos, int length)
18     {
19         if (pos == length)
20         {
21             if (valid(current))
22                 output.push_back(current);
23         }
24         else
25         {
26             current[pos] = '(';
27             generate(current, pos + 1, length);
28             current[pos] = ')';
29             generate(current, pos + 1, length);
30         }
31     }
32     vector<string> generateParenthesis(int n)
33     {
34         string current(2 * n, '');
35         output = vector<string>();
36         generate(current, 0, 2 * n);
37         return output;
38     }
39 };

● 单边加项，3 ms，随时记录当前的 '(' 和 ')' 的数量，其中一个超过 n 的时候立即停止继续深入。前面穷举过程中大部分时间都浪费在了连左右括号数量都不相等的情况中。

 1 class Solution
 2 {
 3 public:
 4     
 5     void backtracking(vector<string>& ans, string s, int l, int r, int n)
 6     {
 7         if (l < n)                                  // 限制了添加 '('  和 ')' 的条件，注意添加过程是两条独立的分支
 8             backtracking(ans, s + "(", l + 1, r, n);
 9         
10         if (r < l)
11             backtracking(ans, s + ")", l, r + 1, n);
12         else if (r == l && l == n)
13             ans.push_back(s);
14         return;
15     }
16     vector<string> generateParenthesis(int n)
17     {
18         vector<string> ans;
19         backtracking(ans, "", 0, 0, n);
20         return ans;
21     }
22 };

● 双边加项的递归，6 ms。每次从较短的合法表达式中取出两个，用 "（" + "左元" + "）" + "右元" 的范式加以组合。

 1 class Solution
 2 {
 3 public:
 4     vector<string> generateParenthesis(int n)
 5     {
 6         vector<string> output;
 7         if (n == 0)
 8         {
 9             output.push_back("");
10             return output;
11         }
12         int i, j, k;
13         string left, right;
14         vector<string> leftVector, rightVector;
15         for (i = 0; i < n; i++)
16         {
17             for (leftVector = generateParenthesis(i), j = 0; j < leftVector.size(); j++)
18             {
19                 left = leftVector[j];
20                 for (rightVector = generateParenthesis(n - 1 - i), k = 0; k < rightVector.size(); k++)
21                 {
22                     right = rightVector[k];
23                     output.push_back("(" + left + ")" + right);// 每次在左堆中取一个，右堆中取一个，结合成 "( 左元 ) 右元" 的形式
24                 }
25             }
26         }        
27         return output;
28     }
29 };

● 双边加项的非递归法，3 ms，免去了反复计算较短合法表达式的过程，但是空间开销大。注意到卡塔兰数的递推性质： a_n = a_n-1 a₀ + a_n-2 a₁ + ... + a_n-2 a₁ + a_n-1 a₀ 。

 1 class Solution
 2 {
 3 public:
 4     vector<string> generateParenthesis(int n)
 5     {
 6         vector<vector<string>> table(n + 1);
 7         table[0] = vector<string>({ "" }); 
 8         int i, j, k, lp;
 9         for (i = 1; i <= n; i++)                                    // write all combinations of i pair of brackets  in row i of variable 'table'
10         {
11             for (lp = 0; lp < i; lp++)                              // size of the left part, from 0 to i-1
12             {
13                 for (j = 0; j < table[lp].size(); j++)              // take one element in row lp as left part           
14                 {
15                     for (k = 0; k < table[i - 1 - lp].size(); k++)  // take one element in row i-1-lp as right part
16                         table[i].push_back("(" + table[lp][j] + ")" + table[i - 1 - lp][k]);
17                 }                                                   // combinate the two parts like Approach #3
18             }
19         }
20         return table[n];
21     }
22 };

● 大佬的回溯法，3 ms，类似单边加项法。

 1 class Solution
 2 {
 3 public:
 4     vector<string> generateParenthesis(int n)
 5     {
 6         vector<string> res;
 7         paren(n, 0, res, "");
 8         return res;
 9     }
10     void paren(int n, int m, vector<string>& res, string str)// n 代表剩余 '(' 数量，m 代表当前 () 层数
11     {
12         if (m == 0 && n == 0)
13         {
14             res.push_back(str);
15             return;
16         }
17         if (n > 0)
18             paren(n - 1, m + 1, res, str + "(");// 尝试添加一个左括号
19         if (m > 0)
20             paren(n, m - 1, res, str + ")");    // 尝试添加一个右括号
21     }
22 };