LeetCode:Generate Parentheses

题目链接

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

所有组合的个数其实是一个卡特兰数。

我们这样来构造一个合法的字符串：首先第一个位置肯定是“（”，对于后面位置:

1、如果前一个字符是“（”：那么我们可以在当前位置上加入“）”（字符“）”一定有剩余）；如果“（”字符还有剩余，也可以在当前位置加入“（” 本文地址

2、如果前一个字符是“）”：如果当前“（”和“）”剩余的数目不同（即其那面的括号没有完全匹配），可以在当前位置上加入“）”；如果“（”字符还有剩余，也可以在当前位置加入“（”

 1 class Solution {
 2 public:
 3     vector<string> generateParenthesis(int n) {
 4         string tmpres(n<<1, '(');
 5         vector<string> res;
 6         helper(1, tmpres, res, n-1, n);
 7         return res;
 8     }
 9 private:
10     void helper(int index, string &tmpres, vector<string>&res, int leftNum, int rightNum)
11     {
12         if(index >= tmpres.size()){res.push_back(tmpres); return;}
13         if(tmpres[index-1] == '(')
14         {
15             tmpres[index] = ')';
16             helper(index+1, tmpres, res, leftNum, rightNum-1);
17             if(leftNum > 0)
18             {
19                 tmpres[index] = '(';
20                 helper(index+1, tmpres, res, leftNum-1, rightNum);
21             }
22         }
23         else
24         {
25             if(leftNum != rightNum)
26             {
27                 tmpres[index] = ')';
28                 helper(index+1, tmpres, res, leftNum, rightNum-1);
29             }
30             if(leftNum > 0)
31             {
32                 tmpres[index] = '(';
33                 helper(index+1, tmpres, res, leftNum-1, rightNum);
34             }
35         }
36     }
37 };

其实对于某个合法的字符串，我们可以发现从合法字符串的任何一个位置看，“（”的数目 >= ")"的数目，即剩余的“（”的数目 <= 剩余的"）"数目, 因此就有以下更加简洁的代码

 1 class Solution {
 2 public:
 3     vector<string> generateParenthesis(int n) {
 4         string tmpres;
 5         vector<string> res;
 6         helper(tmpres, res, n, n);
 7         return res;
 8     }
 9 private:
10     void helper(string &tmpres, vector<string>&res, int leftNum, int rightNum)
11     {
12         if(leftNum > rightNum)return;
13         if(leftNum == 0 && rightNum == 0)
14         {
15             res.push_back(tmpres);
16             return;
17         }
18         if(leftNum > 0)
19         {
20             tmpres.push_back('(');
21             helper(tmpres, res, leftNum-1, rightNum);
22             tmpres.pop_back();
23         }
24         if(rightNum > 0)
25         {
26             tmpres.push_back(')');
27             helper(tmpres, res, leftNum, rightNum-1);
28             tmpres.pop_back();
29         }
30     }
31 };