# 22. Generate Parentheses

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

**Example 1:**

<pre><code><strong>Input: n = 3
</strong><strong>Output: ["((()))","(()())","(())()","()(())","()()()"]
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: n = 1
</strong><strong>Output: ["()"]
</strong></code></pre>

**Constraints:**

* `1 <= n <= 8`

***My Solutions:***

把temp string 加入结果的条件是temp string的长度等于n\*2

解法1：先输入一个（到结果里，把（的数量记做open，)的数量记做close。最多可以加n个（。当open的数量超过close的时候，必须加入close。

```java
public List<String> generateParenthesis(int n) {
    List<String> list = new ArrayList<String>();
    dfs(list,"(", 1, 0, n);
    return list;
}

public void dfs(List<String> list, String temp, int open, int close, int n) {
    if (temp.length() == n * 2) {
        list.add(temp);
        return;
    }
    if (open < n) dfs(list, temp + "(", open + 1, close, n);
    if (open > close) dfs(list, temp + ")", open, close + 1, n);
}
```

解法2：这类型问题的常见解法。

```
public List<String> generateParenthesis(int n) {     
    List<String> result = new ArrayList<>();
    if (n < 1) return result;
    dfs(result, new StringBuilder(), 0, 0, n);
    return result;
}

public void dfs(List<String> result, StringBuilder temp, int open, int close, int n) {
    if (temp.length() == n * 2) {
        result.add(temp.toString());
        return;
    }
    if (open < n) {
        temp.append("(");
        dfs(result, temp, open + 1, close, n);
        temp.deleteCharAt(temp.length() - 1);
    }    
    if (close < open) {
        temp.append(")");
        dfs(result, temp, open, close + 1, n);
        temp.deleteCharAt(temp.length() - 1);
    }
}
```
