题解 | #括号生成#

方法：递归+回溯

n对括号的生成就是n个左括号和n个右括号组成的合法排列，在使用了一个左括号后，还剩n-1个左括号和n个右括号进入子问题递归。但是要保证序列合法，使用的右括号数不能大于左括号，因此需要每次都检查使用的括号数量。

具体做法：

• step 1：将空串与左右括号各自使用了0个送入递归。
• step 2：若是左右括号都使用了n个，此时就是一种结果，添加后返回。
• step 3：若是左括号数没有到达n个，可以考虑增加左括号进入递归，或者右括号数没有到达n个且左括号的使用次数多于右括号就可以增加右括号进入递归。

import java.util.*;
public class Solution {
    public void dfs(ArrayList<String> res,String temp,int n,int left,int right){
        if(left==n&&right==n){
            res.add(new String(temp));
            return;
        }
        if(left<n){
            dfs(res,temp+"(",n,left+1,right);
        }
        if(right<n&&left>right){
            dfs(res,temp+")",n,left,right+1);
        }
    }
    public ArrayList<String> generateParenthesis (int n) {
        ArrayList<String> res = new ArrayList<String>();
        dfs(res,"",n,0,0);

        return res;
    }
}