Leetcode-22.括号生成

发表于 分类于 阅读次数：

题目描述

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

解法1：回溯

只有在我们知道序列仍然保持有效时才添加 ‘(‘ or ‘)’。我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点。

如果我们还剩一个位置，我们可以开始放一个左括号。 如果它不超过左括号的数量，我们可以放一个右括号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
private:
    vector<string> res;
public:
    vector<string> generateParenthesis(int n) {
        backtrack("",0,0,n);
        return res;
        
    }
    void backtrack(string temp,int left,int right,int n)
    {
        if(temp.length()==n*2)
        {
            res.push_back(temp);
            return ;
        }
        if(left<n)
            backtrack(temp+'(',left+1,right,n);
        if(right<left)
            backtrack(temp+')',left,right+1,n);
    }
};

解法2：闭合法

思路

为了枚举某些内容，我们通常希望将其表示为更容易计算的不相交子集的总和。

考虑有效括号序列 S 的 闭包数：至少存在 index >= 0，使得 S[0], S[1], …, S[2*index+1]是有效的。 显然，每个括号序列都有一个唯一的闭包号。 我们可以尝试单独列举它们。

算法

对于每个闭合数 c，我们知道起始和结束括号必定位于索引 0 和 2c + 1。然后两者间的 2c 个元素一定是有效序列，其余元素一定是有效序列。

作者：LeetCode
链接：https://leetcode-cn.com/problems/generate-parentheses/solution/gua-hao-sheng-cheng-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        if(n==0)
            ans.push_back("");
        else
        {
            for(int a=0;a<n;a++)
            {
                for(string left:generateParenthesis(a))
                    for(string right:generateParenthesis(n-1-a))
                        ans.push_back("("+left+")"+right);
            }
        }
        return ans;
    }
};