题解 | #括号生成#

本题采用的是回溯+剪枝。生成括号我们可以看作将大问题分解为小问题，使用递归的思想解决，但在生成时需要满足生成的右括号小于等于左括号数才是有效的，利用该特点进行剪枝。

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    public ArrayList generateParenthesis (int n) {
        // write code here
        ArrayList list = new ArrayList();
        if(n==0){
            list.add("");
            return list;
        }
        generateAll(n,n,"",list);
        return list;
    }
    //left,right表示当前需要生成的剩余的左括号，右括号数
    public void generateAll(int left,int right,String str,List list){
        if(left == 0 && right == 0){ //结束条件
            list.add(str);
            return;
        }
        if(left>0){
            generateAll(left-1,right,str+"(",list);
        }
        if(right>left){
            generateAll(left,right-1,str+")",list);
        }
    }
}