题解 | #括号生成#

先放左括号，每个右括号前面都要有一个没使用的左括号跟它抵消。
具体实现，回溯，设置一个标志位flag=0，表示左括号的数量。思想是放入左括号flag++，放入右括号flag--。如果flag小于0那么这个序列肯定已经不合法了，没有添加下去的必要了。这是因为每次放右括号都需要前面有一个没使用的左括号跟它抵消。flag小于0表示左括号已经被后来放入的右括号抵消完了，这次先放入了右括号（不合法）。
public class Solution {
    /**
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        ArrayList<String> res=new ArrayList<>();
        StringBuffer str=new StringBuffer();
        process(res,str,2*n,0);
        return res;
    }
    public void process(ArrayList<String> res,StringBuffer str,int len,int flag){
        if(len<0||flag<0)return;//这里是出口，len<0要不然如果一值添加左括号。flag<0,序列已经不合法了，没有接下去添加的必要了
        if(len==0&&flag==0){
            res.add(new String(str));
        }
//         if(flag==0){
//             str.append("(");
//             process(res,str,len-1,flag+1);
//             str.deleteCharAt(str.length()-1);
//         }else if(flag>0){
//             str.append("(");
//             process(res,str,len-1,flag+1);
//             str.deleteCharAt(str.length()-1);
//             str.append(")");
//             process(res,str,len-1,flag-1);
//             str.deleteCharAt(str.length()-1);
//         }
        str.append("(");
        process(res,str,len-1,flag+1);
        str.deleteCharAt(str.length()-1);
        str.append(")");
        process(res,str,len-1,flag-1);
        str.deleteCharAt(str.length()-1);
    }
}