题解 | #括号生成#

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    public ArrayList<String> generateParenthesis (int n) {
        ArrayList<String> list = new ArrayList<>();
        StringBuilder sub = new StringBuilder();
        dfs(list,sub,2*n,0,n,n);
        return list;
    }
    
    private void dfs(ArrayList<String> list,StringBuilder sub,int size,int index,int l_count,int r_count){
        if(l_count < 0 || r_count < 0) return ;
        if(index == size){
            list.add(sub.toString());
            return ;
        }
        if(l_count <= r_count){// 当( 剩余的多于 ) 
            sub.append(')');
            dfs(list,sub,size,index + 1,l_count,r_count-1);
            sub.deleteCharAt(index);
            
            sub.append('(');
            dfs(list,sub,size,index + 1,l_count-1,r_count);
            sub.deleteCharAt(index);
           
        }else {
            sub.append(')');
            dfs(list,sub,size,index + 1,l_count,r_count-1);
            sub.deleteCharAt(index);
        }
        
    }
}