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

My Solutions:

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

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

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);
    }
}