题解 | #括号生成#

合法的括号序列需要满足两个条件：

1. 序列的左右括号数量相同
2. 序列的任一个前缀的左括号数量不少于右括号数量 基于此，使用DFS求解。代码如下：

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    ArrayList<String> res = new ArrayList<>();
    int n;
    public ArrayList<String> generateParenthesis (int _n) {
        // write code here
        n = _n;
        dfs("",0,0);
        return res;
    }
    
    public void dfs(String s,int cnt1,int cnt2) {
        if(cnt1 == n && cnt2 == n) {
            res.add(s);
            return;
        }
        if(cnt1 < n) {
            dfs(s+"(",cnt1+1,cnt2);
        }
        if(cnt1 > cnt2 && cnt2 < n) {
            dfs(s+")",cnt1,cnt2+1);
        }
    }
}