题解 | #括号生成#

两种思路解决，首先大思路肯定是递归法，因为要得到所有合法的排列组合。

思路：

1. 经典的递归实现加剪枝，用map存储当前剩余的左右括号数，然后递归过程中添加括号，并事实更新当前组合的括号情况，用cnt来代表，左括号就为cnt+1，右括号cnt-1，cnt为0说明当前是合法组合，递归终止的条件是字符串长度等于2*n，接着判断若cnt为0就加入结果集中。可以加入剪枝若cnt已经小于0，说明当前字符串必然不是合法组合（因为左括号数小于右括号），此时其实可以去掉递归判断的cnt==0加入结果集条件。
2. 不用map存储括号数，直接用两个参数传递此时剩余的括号，节约空间，同时由于不用遍历map集合，效率要高于第一种。递归过程有点类似于二叉树的先序遍历，在组成括号的过程中先遍历左括号，只要左括号不为0就继续添加左括号，递归退出的判断是左右括号都为0，或者剩余的左括号大于右括号（说明前面添加的右括号大于左括号），已经不是合法的括号组合。注意此时递归退出的第二个条件是必须的，它不是起到剪枝作用，而是阻止出现非法的括号组合。

代码：

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    HashMap<String,Integer> map;
    public ArrayList<String> generateParenthesis (int n) {
        //思路2，不用map存储括号数，直接用两个参数传递此时剩余的括号
        ArrayList<String> res=new ArrayList<String>();
        dfs1(res,new StringBuilder(),n,n);
        return res;
//         //思路1，经典的递归实现加剪枝
//         map=new HashMap<>();
//         map.put("(",n);
//         map.put(")",n);
//         ArrayList<String> res=new ArrayList<String>();
//         dfs(res,new StringBuilder(),2*n,0);//n对括号组成的组合长度为2*n
//         return res;
    }
    //有点类似于二叉树的先序遍历，在组成括号的过程中先遍历左括号，只要左括号不为0就继续添加左括号，
    //递归退出的判断是左右括号都为0，或者剩余的左括号大于右括号（说明前面添加的右括号大于左括号），
    //已经不是合法的括号组合
    private void dfs1(ArrayList<String> res,StringBuilder sb,int left,int right){
        if(left==0&&right==0){
            res.add(new String(sb));
            return;
        }
        if(left>right){
            return;
        }
        if(left>0){
            sb.append("(");
            dfs1(res,sb,left-1,right);
            sb.deleteCharAt(sb.length()-1);
        }
        if(right>0){
            sb.append(")");
            dfs1(res,sb,left,right-1);
            sb.deleteCharAt(sb.length()-1);
        }
    }
    
    //cnt代表当前的括号组成情况，大于零说明左括号大于右括号数，等于说明相等。
    private void dfs(ArrayList<String> res,StringBuilder sb,int n2,int cnt){
        if(sb.length()==n2){
            if(cnt==0){
                res.add(new String(sb));
            }
            return;
        }
        if(cnt<0){
            return;
        }
        for(String key:map.keySet()){
            int n;
            if((n=map.get(key))>0){
                if("(".equals(key)){
                    sb.append(key);
                    map.put(key,n-1);
                    dfs(res,sb,n2,cnt+1);
                    sb.deleteCharAt(sb.length()-1);
                    map.put(key,n);
                }else{
                    sb.append(key);
                    map.put(key,n-1);
                    dfs(res,sb,n2,cnt-1);
                    sb.deleteCharAt(sb.length()-1);
                    map.put(key,n);
                }
            }
        }
    }
}