# 22. Generate Parentheses

Given `n` pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

``````**Input:** n = 3
**Output:** ["((()))","(()())","(())()","()(())","()()()"]
``````

Example 2:

``````**Input:** n = 1
**Output:** ["()"]
``````

Constraints:

• `1 <= n <= 8`

C++ 解法一：

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

Java 解法一：

``````public class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<String>();
helper(n, n, "", res);
return res;
}
void helper(int left, int right, String out, List<String> res) {
if (left < 0 || right < 0 || left > right) return;
if (left == 0 && right == 0) {
return;
}
helper(left - 1, right, out + "(", res);
helper(left, right - 1, out + ")", res);
}
}
``````

n＝1: ()

n=2: (()) ()()

n=3: (()()) ((())) ()(()) (())() ()()()

C++ 解法二：

``````class Solution {
public:
vector<string> generateParenthesis(int n) {
unordered_set<string> st;
if (n == 0) st.insert("");
else {
vector<string> pre = generateParenthesis(n - 1);
for (auto a : pre) {
for (int i = 0; i < a.size(); ++i) {
if (a[i] == '(') {
a.insert(a.begin() + i + 1, '(');
a.insert(a.begin() + i + 2, ')');
st.insert(a);
a.erase(a.begin() + i + 1, a.begin() + i + 3);
}
}
st.insert("()" + a);
}
}
return vector<string>(st.begin(), st.end());
}
};
``````

Java 解法二:

``````public class Solution {
public List<String> generateParenthesis(int n) {
Set<String> res = new HashSet<String>();
if (n == 0) {
} else {
List<String> pre = generateParenthesis(n - 1);
for (String str : pre) {
for (int i = 0; i < str.length(); ++i) {
if (str.charAt(i) == '(') {
str = str.substring(0, i + 1) + "()" + str.substring(i + 1, str.length());
str = str.substring(0, i + 1) +  str.substring(i + 3, str.length());
}
}
}
}
return new ArrayList(res);
}
}
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/22

Remove Invalid Parentheses

Longest Valid Parentheses

Valid Parentheses

Score of Parentheses

Valid Parenthesis String

Letter Combinations of a Phone Number

Check if a Parentheses String Can Be Valid

https://leetcode.com/problems/generate-parentheses/

https://leetcode.com/problems/generate-parentheses/discuss/10127/An-iterative-method.

https://leetcode.com/problems/generate-parentheses/discuss/10337/My-accepted-JAVA-solution

https://leetcode.com/problems/generate-parentheses/discuss/10105/Concise-recursive-C%2B%2B-solution

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation