1. 题目介绍（括号生成）

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

【Translate】： 给定n对括号，写一个函数来生成所有格式良好的括号的组合。

【测试用例】：
test
【约束】：
Constraints

2. 题解

2.1 递归

??brobins9提供的题解 Easy to understand Java backtracking solution

主要思想：The idea here is to only add ‘(’ and ‘)’ that we know will guarantee us a solution (instead of adding 1 too many close). Once we add a ‘(’ we will then discard it and try a ‘)’ which can only close a valid ‘(’. Each of these steps are recursively called.

伪代码转化：

The code will be:

//base case
if(string length == 2*n) {
	add(string);
	return;
}
//recursive case
if(number of “(“s < n){
	add a “(“
}
if(number of “(“s > number of “)”s){
	add a “)"
}

// an example to understand this solution:
	(
	((
	(((
	((()
	((())
	((()))
	(()
	(()(
	(()()
	(()())
	(())
	(())(
	(())()
	()
	()(
	()((
	()(()
	()(())
	()()
	()()(
	()()()

    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<String>();
        backtrack(list, "", 0, 0, n);
        return list;
    }
    
    public void backtrack(List<String> list, String str, int open, int close, int max){
        
        if(str.length() == max*2){
            list.add(str);
            return;
        }
        
        if(open < max)
            backtrack(list, str+"(", open+1, close, max);
        if(close < open)
            backtrack(list, str+")", open, close+1, max);
    }

case1

2.2 Iterative

??left_peter提供的题解 An iterative method. 该方法的思想DP。首先考虑如何从前面的结果f(0)…f(n-1)得到结果f(n)。实际上，结果f(n)和f(n-1)加了一个()对。让"(“总是在第一个位置，为了产生一个有效的结果，我们只能将”)"以这样一种方式放置:在额外的()里面有i对()，在额外的()外面有n - 1 - i对()。

f(0): ""

f(1): "("f(0)")"

f(2): "("f(0)")"f(1), "("f(1)")"

f(3): "("f(0)")"f(2), "("f(1)")"f(1), "("f(2)")"

So f(n) = "("f(0)")"f(n-1) , "("f(1)")"f(n-2) "("f(2)")"f(n-3) ... "("f(i)")"f(n-1-i) ... "(f(n-1)")"

   public List<String> generateParenthesis(int n)
    {
        List<List<String>> lists = new ArrayList<>();
        lists.add(Collections.singletonList(""));
        
        for (int i = 1; i <= n; ++i)
        {
            final List<String> list = new ArrayList<>();
            
            for (int j = 0; j < i; ++j)
            {
                for (final String first : lists.get(j))
                {
                    for (final String second : lists.get(i - 1 - j))
                    {
                        list.add("(" + first + ")" + second);
                    }
                }
            }
            
            lists.add(list);
        }
        
        return lists.get(lists.size() - 1);
    }