Generate Parentheses

Q:
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:
"((()))", "(()())", "(())()", "()(())", "()()()"

A:
--------------Recursively call  产生各种情况，同时检测是否正确-------------------
 ----------------------3 rd Pass. ----------------------
最新的思路是这样的 ：  3 = （2）[即单独3]  or 2+1 or 1+2   or 1+1+1
对每个n , 可以写成的加和的方式为f(n)
则f(n) = ( f(n-1)   ) （f(n-1）外边加括号
           + f(i)  * f(n-i)    i = 1,2....n-1
头脑不清晰，先用试错的方法先写完的。

public class Solution {
    public ArrayList<String> generateParenthesis(int n) {
        ArrayList<String> al = new ArrayList<String>();
        int nLeft = 1, nRight = 0;
        getBrace("(", nLeft,nRight,n,al);
        return al;
    }
    private void getBrace(String str, int nLeft,int nRight,int n,ArrayList<String> al){
        if(nLeft < nRight || nRight>n || nLeft>n)
            return;
        if(nLeft == nRight && nLeft == n)
            al.add(str);
        getBrace(str+"(", nLeft+1,nRight,n, al);
        getBrace(str+")", nLeft,nRight+1,n , al);
    }
}

用char Array，save more space

public class Solution {
    public List<String> generateParenthesis(int n) {
        char[] A = new char[n+n];
        List<String> list = new LinkedList();
        dfs(A,list,n,n);
        return list;
    }
    private void dfs(char[] A, List<String> list, int nLeft, int nRight){
        if(nLeft > nRight || nLeft<0 || nRight<0) 
            return;
        if(nLeft ==0 && nRight ==0){
            list.add(new String(A));
            return;
        }
        int i = A.length - nLeft-nRight;
        A[i] = '(';
        dfs(A,list,nLeft-1,nRight);
        A[i] = ')';
        dfs(A,list,nLeft, nRight-1);
    }
}

-------------Iterative call -----------------但是思想跟recursive一样, 用了stack保存----------------

 public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> list  = new LinkedList();
        
        List<String> queue = new LinkedList();
        List<int[]> queue2 = new LinkedList();
        queue.add("");
        int[] arr = new int[2];
        queue2.add(arr);
        while(!queue.isEmpty()){
            String str = queue.remove(0); // pull
            int[] A = queue2.remove(0);
            int leftUsed = A[0], rightUsed = A[1];
            if(leftUsed >n || rightUsed > n || leftUsed < rightUsed)
                continue;
            if(leftUsed == n && rightUsed == n)
                list.add(str);
                
            queue.add(str+"(");
            int[] left2 = {leftUsed+1,rightUsed};
            queue2.add(left2);
            
            queue.add(str+")");
            int[] right2 = {leftUsed,rightUsed+1};
            queue2.add(right2);
        }
        return list;
    }
}

就是 递归，将 n 简化为n-1 ------------这个思路不对。
"((()))", "(()())", "(())()", "()(())", "()()()"
0 = ""
1= "()"

2 = 1+1
2 = 2

3 = 1 + 1 + 1  
3 = 1 + 2 --------------->2 is  ( 1 )
3 = 2 + 1
3 = 3   ---> 最外面的一个paranthesis中包含了( 2 )

----------------就是先加入一个，然后递归调用,先前的，基于递归效率不高， 想用DP算法的方法，没有搞定。
这个题目最终的结果数目是 Catalan number

http://en.wikipedia.org/wiki/Catalan_number





---------------第二遍---------- DP 方法--------  ------
对于第一遍所遇到的， duplicate的问题， 我们用了 Set 来解决。

public class Solution {
    public ArrayList<String> generateParenthesis(int n) {
        // DP , pre-calculated list are in all
        ArrayList<ArrayList<String>> all = new ArrayList<ArrayList<String>>();
        ArrayList<String> al = new ArrayList<String>();
        al.add("()");
        all.add(al);// add the case when n ==1, coz we do not want the

        for (int i = 1; i < n; i++) {
            al = new ArrayList<String>();            
            ArrayList<String> preAl = all.get(i - 1);
            for (int j = 0; j < preAl.size(); j++)
                al.add("(" + preAl.get(j) + ")");

            // add other combinations
            for (int j = 0; j < i; j++) {
                int k = i - j - 1;// minus 1 , coz i,j are index,
                ArrayList<String> left = all.get(j);
                ArrayList<String> right = all.get(k);
                for (int jj = 0; jj < left.size(); jj++)
                    for (int kk = 0; kk < right.size(); kk++)
                        al.add(left.get(jj) + right.get(kk));
            }
            // remove duplicates
            HashSet<String> set = new HashSet<String>();
            set.addAll(al);
            al.clear();
            al.addAll(set);
            
            all.add(al);
        }
        return all.get(n - 1);
    }
}

Mistakes:
1:  递归的时候，开始仅仅假设了两种情况
()+oneLess
( + oneLess + ) 
 还有一种情况，就是 ()加在后边 (这时候，有可能有重复，）

2：  n ==4 ---》 有一种情况， 是(())(())  是不能分成  n ==3 的情况的。  思路不对啊。应该是2+2   （基于DP的 一个个加上来的 算法）


Learned: