# 22. Generate Parentheses (Medium)

https://leetcode.com/problems/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:

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

## Solutions

``````class Solution {

// To form a valid parentheses pattern,  the open parentheses must be equal or more than close parentheses
// during the process of generating the combination.

public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList<>();
if (n == 0) {
return ans;
}

if (n == 1) {

return ans;
}

Stack<String> track = new Stack<>();

recurse(n, n, track, ans);

return ans;
}

private void recurse(int openP, int closeP, Stack<String> track, List<String> ans) {
// openP represents how many open parentheses left, closeP is the close parentheses that left.

if (openP < 0 || closeP < 0) {
return;
}

// all the left and right parentheses are used up.
if (openP == 0 && closeP == 0) {
String s = "";
for (int i = 0; i < track.size(); i++) {
s += track.get(i);
}

return;
}

track.push("(");
recurse(openP - 1, closeP, track, ans);
track.pop();

// append close parentheses thereafter
if (openP < closeP) {
track.push(")");
recurse(openP, closeP - 1, track, ans);
track.pop();
}
}
}
``````