【leetcode刷题】T65-括号生成

木又AI帮

修改于 2019-07-18 02:12:49

34200

代码可运行

文章被收录于专栏：木又AI帮木又AI帮

运行总次数：0

代码可运行

【题目】

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

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

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

【思路】

什么是有效的括号？可以参考【T19-有效的括号】。

可以这样理解：从左往右对元素进行计数，左括号的个数始终大于等于右括号的个数。

有一个很自然的想法，使用递归，使用变量left和right分别存储左括号和右括号剩余可用个数，当left>0，继续递归（left-1）；当right>left，继续递归（right-1）；当left和right都为0，满足条件，加入结果。

【代码】

python版本

class Solution(object):
    def loop(self, sub, res, left, right):
        if left ==  and right == :
            res.append(sub)
            return
        # 还有左括号
        if left > :
            self.loop(sub+'(', res, left-1, right)
        # 右括号数大于左括号数
        if right > left:
            self.loop(sub+')', res, left, right-1)

    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        res = []
        self.loop('', res, n, n)
        return res

C++版本

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        loop("", res, n, n);
        return res;
    }

    void loop(string s, vector<string>& res, int left, int right){
        if(left ==  && right == ){
            res.push_back(s);
            return ;
        }
        // 还有左括号
        if(left > )
            loop(s + "(", res, left-1, right);
        // 右括号数大于左括号数
        if(right > left)
            loop(s + ")", res, left, right-1);
    }
};