LeetCode第21题之Generate Parentheses（两种解法）

本文主要是介绍LeetCode第21题之Generate Parentheses（两种解法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

C++代码：
解法一（在LeetCode上运行效率高于解法二）：

#include <vector>
#include <iostream>
#include <string>
using namespace std;class Solution {
private:vector<string> res;
public: //leftRemain保存还可以放左括号的数目，rightRemain保存还可以放右括号的数目void dfs(string state, int leftRemain, int rightRemain){//这种情况括号不匹配if (leftRemain > rightRemain){return;}if (0 == leftRemain && 0 == rightRemain){res.push_back(state);return;}if (leftRemain > 0){dfs(state + "(", leftRemain -1, rightRemain);}if (rightRemain >0 ){dfs(state + ")", leftRemain, rightRemain-1);}}vector<string> generateParenthesis(int n) {dfs("",n,n);return res;}
};int main()
{Solution s;vector<string> r = s.generateParenthesis(3);for (vector<string>::iterator it = r.begin();it != r.end();++it){cout<<*it<<endl;}return 0;
}

解法二：

#include <vector>
#include <iostream>
#include <string>
using namespace std;class Solution {
private://保存结果vector<string> res;
public:void fun(int deep, int n, int leftNum, int leftTotalNum, string s){//如果左括号的总数大于n,则该字符串不可能满足要求if (leftTotalNum  > n){return;}//如果到达最底层,则s一定满足题意。因为运行到这里时，leftTotalNum<=n,而leftNum>=0if (n*2 == deep){res.push_back(s);return;}for (int i=0;i<2;++i){if (0 == i){//在deep+1的位置放左括号fun(deep+1, n, leftNum+1, leftTotalNum+1, s + "(");}else{//如果有剩余未匹配的左括号数，才能放右括号if (leftNum > 0){fun(deep+1, n, leftNum-1, leftTotalNum, s + ")");}}}}vector<string> generateParenthesis(int n) {//剩余未匹配的左括号数int leftNum = 0;//字符串中左括号总数int leftTotalNum =0;string s = "";fun(0, n, leftNum, leftTotalNum, s);return res;}
};int main()
{Solution s;vector<string> r = s.generateParenthesis(3);for (vector<string>::iterator it = r.begin();it != r.end();++it){cout<<*it<<endl;}return 0;
}