# 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:

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

## Java Solution 1 – DFS

This solution is simple and clear. In the dfs() method, left stands for the remaining number of (, right stands for the remaining number of ).

```public List<String> generateParenthesis(int n) {
ArrayList<String> result = new ArrayList<String>();
dfs(result, "", n, n);
return result;
}
/*
left and right represents the remaining number of ( and ) that need to be added.
When left > right, there are more ")" placed than "(". Such cases are wrong and the method stops.
*/
public void dfs(ArrayList<String> result, String s, int left, int right){
if(left > right)
return;

if(left==0&&right==0){
return;
}

if(left>0){
dfs(result, s+"(", left-1, right);
}

if(right>0){
dfs(result, s+")", left, right-1);
}
}
```

Generate Parentheses Java Solution 2

## This solution looks more complicated. You can use n=2 to walk through the code.

```public List<String> generateParenthesis(int n) {
ArrayList<String> result = new ArrayList<String>();
ArrayList<Integer> diff = new ArrayList<Integer>();

for (int i = 0; i < 2 * n; i++) {
ArrayList<String> temp1 = new ArrayList<String>();
ArrayList<Integer> temp2 = new ArrayList<Integer>();

for (int j = 0; j < result.size(); j++) {
String s = result.get(j);
int k = diff.get(j);

if (i < 2 * n - 1) {
}

if (k > 0 && i < 2 * n - 1 || k == 1 && i == 2 * n - 1) {
}
}

result = new ArrayList<String>(temp1);
diff = new ArrayList<Integer>(temp2);
}

return result;
}
```

Object-oriented programming offers a sustainable way to write spaghetti code. It lets you accrete programs as a series of patches.”
― Paul Graham, Hackers & Painters: Big Ideas from the Computer Age

You can also check out Longest Valid Parentheses