题解 | #括号生成#

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */

    /**
    思路：使用递归 递归的终止条件就是使用了n个左括号和n个右括号
    每次添加阔号有两种情况 要么添加左括号 要么添加右括号
    当然 添加右括号存在限制 必须已经加入的 左括号大于右括号 才能加入右括号 否则会出现非法情况

    题目特殊 不涉及到某些条件的加持与释放 类似于二叉树的深度优先
     */
    ArrayList<String> res = new ArrayList<String>(); 
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        recursion(0,0,"",n);
        return res;
    }

    void recursion(int left, int right,String s ,int n){
        if(left == n && right == n){
            res.add(s);
            return;
        }
        if(left < n){
             recursion(left+1,right,s+'(',n);
        }
        if(right < n && left > right){
             recursion(left,right+1,s+')',n);
        }
    }


}