题解 | #括号生成，递归，剪枝#

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    public ArrayList<String> generateParenthesis (int n) {
        ArrayList<String> res = new ArrayList<>() ;
        help(n , 0 , 0 , new StringBuilder() , res) ;
        return res ;
    }
    //思想：1.对于每一个位置，要么是左括号，要么是右括号，只有这么两种情况；
    //2.对于每一个位置上，我们可以尝试添加左括号，并记录左括号的使用次数;同理也可以添加右括号；
    //3.在某刻位置上若发现左括号已用完，但右括号还没用完，则说明当前已经不合法，终止递归；
    //4.合法的括号字符串拼接完成前，左括号的使用次数一定是大于右括号的，利用这个条件，
    //若在某个位置发现右括号的次数大于了左括号，或者是说右括号次数已经大于了括号对数，说明不合法，
    //终止递归。
    //n对括号的排法（left是左括号的使用数量，right是有括号的使用数量）
    public void help(int n , int left , int right , StringBuilder sb , ArrayList<String> res) {
        if(left == n && right == n) {//当左右括号数量等于括号的对数，说明满足要求，保存结果
            res.add(new String(sb)) ;
            return ;
        }
        //剪枝
        if(left < n) {//只有左括号没用完的时候才添加左括号
            help(n , left + 1 , right , sb.append("(") , res) ;
            sb.deleteCharAt(sb.length() - 1) ;
        }
        //剪枝
        if(right < n && right < left) {//当又括号小于左括号，而且右括号没用完是才能添加右括号
            help(n , left , right + 1 , sb.append(")") , res) ;
            sb.deleteCharAt(sb.length() - 1) ;
        }
    }
}