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:

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

括號匹配。使用遞歸的方法。

設定left、right表示左右括號的剩余數，

如果left > right表示匹配失衡，直接返回。

如果left < right表示已經存在一個左括號，需要匹配下一次左括號或者右括號，進行遞歸。

如果left == right == 0，表示括號匹配完畢且合法。把當前括號序列放入結果數組中。

參考代碼如下：

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

另一種方法，提前剪枝，思路更清晰,left、right表示當前左右括號的數量

class Solution { public:vector<string> generateParenthesis(int n) {vector<string> res;string out;dfs(n, 0, 0, out, res);return res;}void dfs(int n, int left, int right, string out, vector<string>& res){if (left < n){out.push_back('(');dfs(n, left+1, right, out, res);out.pop_back();}if (left > right){out.push_back(')');dfs(n, left, right+1, out, res);out.pop_back();}if (out.size() == n*2)res.push_back(out);} };

?

轉載于:https://www.cnblogs.com/immjc/p/9454370.html

總結

以上是生活随笔為你收集整理的[LeetCode] Generate Parentheses的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。