22. 括号生成 (opens new window)

1.dfs

分析：深搜通过score分数控制括号匹配的合法问题，如果遇到左括号则score加一，右括号则score减一。模拟了栈的功能。

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res=new ArrayList<>();
        dfs(res,"",n,0);
        return res;
    }
    public void dfs(List<String> res,String curr,int n,int score){
        if(n==0&&score==0){
            res.add(curr);
            return;
        }
        if(score==0){
            dfs(res,curr+"(",n-1,score+1);
        }
        else{
            //继续加左括号
            if(n>0)dfs(res,curr+"(",n-1,score+1);
            //继续加右括号
            dfs(res,curr+")",n,score-1);
        }
    }
}