【LeetCode】No.22. Generate Parentheses -- Java Version

题目链接： https://leetcode.com/problems/generate-parentheses/

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

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

【测试用例】：

【约束】：

  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 generateParenthesis(int n) {
        List list = new ArrayList();
        backtrack(list, "", 0, 0, n);
        return list;
    }
    
    public void backtrack(List 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);
    }

  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 generateParenthesis(int n)
    {
        List> lists = new ArrayList<>();
        lists.add(Collections.singletonList(""));
        
        for (int i = 1; i <= n; ++i)
        {
            final List 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);
    }