2

## 【小馬的LeetCode練功坊】22. Generate Parentheses (Medium)

``````input: n = 3
output:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
``````

# C++解法(窮舉法、4ms)

``````class Solution {
struct parenthesis{
string expr;
int left;
int right;
};
public:
vector<string> generateParenthesis(int n) {
deque<parenthesis> res = {{"(",1,0}};
while(res.front().left< n || res.front().right< n){
parenthesis p = res.front();
string c = p.expr;
int left = p.left, right=p.right;
res.pop_front();
if(left<n){
res.push_back({c+'(', left+1, right});
}
if(right<n && left>right)
res.push_back({c+')', left, right+1});
}
vector<string> ans;
for(auto r: res){
ans.push_back(r.expr);
}
return ans;
}
};
``````

# python 解法(窮舉法、24ms)

``````from collections import deque
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res = deque([('(',1,0)])
while res[0][1]< n or res[0][2]< n:
c, left, right = res.popleft()
if left<n:
res.append((c+'(', left+1, right))
if right<n and left>right:
res.append((c+')', left, right+1))
return [r[0] for r in res]
``````

# zerojudge類似題的解析

(所以說感覺某些問題zerojudge比leetcode還要難，程式執行時間有些嚴格)

## 解法一: 用leetcode上的解存下所有的答案(TLE, 超時)

``````#include <iostream>
#include <vector>
#include <string>
#include <deque>
using namespace std;

struct parenthesis{
string expr;
int left;
int right;
};

vector<string> generateParenthesis(int n) {
deque<parenthesis> res = {{"(",1,0}};
while(res.front().left< n || res.front().right< n){
parenthesis p = res.front();
string c = p.expr;
int left = p.left, right=p.right;
res.pop_front();
if(left<n){
res.push_back({c+'(', left+1, right});
}
if(right<n && left>right)
res.push_back({c+')', left, right+1});
}
vector<string> ans;
for(auto r: res){
ans.push_back(r.expr);
}
return ans;
}

int main()
{
int n;
while(cin >> n){
vector<string> result= generateParenthesis(n);
for(string r : result){
cout<<r<<endl;
}
}
return 0;
}
``````

## 解法二: 節省空間，搜到答案即印出(AC)

``````#include <iostream>
#include <string>
using namespace std;

void generateParenthesis(string &res, int left, int right, int n) {
if(left==n && right==n){
printf("%s\n", res.c_str());
return;
}
int now = left+right;
if(left<n){
res[now]='(';
generateParenthesis(res, left+1, right, n);
}
if(right<n && left>right){
res[now]=')';
generateParenthesis(res, left, right+1, n);
}
}

int main()
{
int n;
while(scanf("%d", &n)!= EOF){
string res(2*n, '0');
generateParenthesis(res, 0, 0, n);
}
return 0;
}
``````