# Question

Formatted question description: https://leetcode.ca/all/22.html

22	Generate Parentheses

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:

"((()))", "(()())", "(())()", "()(())", "()()()"

@tag-string


# Algorithm

This kind of problem of listing all the results should first consider recursive to solve, because the string has only two characters:

• left and right parentheses, and the final result must be 3 left parentheses and 3 right parentheses, so two are defined here The variables left and right respectively represent the number of left and right parentheses.

If the number of left parentheses is greater than the number of right parentheses in a certain recursion, it means that the number of right parentheses in the generated string is greater than the number of left parentheses. Number, an illegal string like )( will appear, so this case will be returned directly without further processing.

If both left and right are 0, it means that the generated string has 3 left brackets and 3 Right parenthesis, and the string is legal, it will be stored in the result and returned. If the above two conditions are not met, if left is greater than 0 at this time, then call the recursive function, pay attention to the update of the parameters, if right is greater than 0, call recursion Function, also update the parameters.

# Code

Java

• import java.util.ArrayList;
import java.util.List;

public class Generate_Parentheses {

public class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<String>();
dfs(n, n, "", res);
return res;
}

void dfs(int left, int right, String out, List<String> res) {
if (left < 0 || right < 0 || left > right) return;
if (left == 0 && right == 0) {
return;
}
dfs(left - 1, right, out + "(", res);
dfs(left, right - 1, out + ")", res);
}
}
}


• // OJ: https://leetcode.com/problems/generate-parentheses/
// Time: O(C(N)) where C(N) is the Nth Catalan number
// Space: O(N)
class Solution {
private:
vector<string> ans;
void generate(int leftCnt, int rightCnt, string &s) {
if (!leftCnt && !rightCnt) {
ans.push_back(s);
return;
}
if (leftCnt) {
s.push_back('(');
generate(leftCnt - 1, rightCnt, s);
s.pop_back();
}
if (rightCnt > leftCnt) {
s.push_back(')');
generate(leftCnt, rightCnt - 1, s);
s.pop_back();
}
}
public:
vector<string> generateParenthesis(int n) {
string s;
generate(n, n, s);
return ans;
}
};

• class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""

def dfs(left, path, res, n):
if len(path) == 2 * n:
if left == 0:
res.append("".join(path))
return

if left < n:
path.append("(")
dfs(left + 1, path, res, n)
path.pop()
if left > 0:
path.append(")")
dfs(left - 1, path, res, n)
path.pop()

res = []
dfs(0, [], res, n)
return res