LEETCODE算法22.Generate Parenthesese

发表于 更新于 分类于 Waline： 阅读次数：

题目

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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
//深度优先搜索，限制条件为左括号小于括号数可以添加一个左括号，右括号小于现有的左括号时可以添加一个右括号
class Solution {
    void gen(vector<string> &re,string &temp,int l,int r,int n)
    {
        if(temp.length()==n*2)
        {
            re.push_back(temp);
        }
        if(l<n){
            temp+='(';
            gen(re,temp,l+1,r,n);
            temp.pop_back();
        }
        if(r<l){
            temp+=')';
            gen(re,temp,l,r+1,n);
            temp.pop_back();
        }
    }
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        string tmp;
        gen(res,tmp,0,0,n);
        return res;
    }
};

//参见评论更加高效的办法，就是没有重复push_back和pop_back了,原理完全相同
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        func(res, "", 0, 0, n);
        return res;
    }
    
    void func(vector<string> &res, string str, int l, int r, int n){
        if(l > n || r > n || r > l) return ;
        if(l == n && r == n) {res.push_back(str); return;}
        func(res, str + '(', l+1, r, n);
        func(res, str + ')', l, r+1, n);
        return;
    }
};

动态规划

  • 动态规划其实类似于归纳法
  • 设i=n时，(a)b为当前所有可能的组合，a和b一共含有n对括号且可以为0，相当于去除第一对括号组合
  • 这样我们就可以去考虑a和b分别的可能性了，然而a和b同时分别是i对和j对括号的所有可能性(i+j=n-1)。

这样我们就有两种思路，一种直接求i=n,然后取出第一对括号后递归查找（可以保存中间结果节约时间），这就是官方题解3；第二种是从i=1开始查找所有配对可能直到i=n,这就是动态规划，原理其实一样的，一个用了系统的栈，一个自己从头遍历，目测用时应该差距不大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//动态规划
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<vector<string>> ans(n+1);
        ans[0].push_back("");
        for(int i=1;i<=n;i++)
        {//查询1对到n对括号的所有可能排列
            for(int j=0;j<i;j++)
            {//拼接当前i对口罩所有可能排列
                for(auto t:ans[j])
                {
                    for(auto tt:ans[i-j-1])
                    {
                        ans[i].push_back('('+t+')'+tt);
                    }
                }
            }
        }
        return ans[n];
    }
};