22.generate_parentheses.md

To Index

22.Generate Parentheses

难度:Medium

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

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

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

动态规划，可以将已有的有效括号分成左右两部分有效括号，然后在左右分别插入左右括号。这样可以生成下一个长度的有效括号对。

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        if(n ==0) res.push_back("");
        else
        {
            for(int i=0;i<n;i++)
            for(auto left: generateParenthesis(i))
            for(auto right: generateParenthesis(n-i-1))
            res.push_back( '('  +left+ ')' + right );
        }
        return res;
    }
};

执行用时 :12 ms, 在所有 C++ 提交中击败了60.89%的用户
内存消耗 :15.4 MB, 在所有 C++ 提交中击败了84.63%的用户