括号生成

括号生成

题目：
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例：

输入：n = 3
输出：[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

解题思路：用回溯解决，不好想到的是方法中传入左括号和右括号剩下的数量

class Solution {
    private List<String> ans = new ArrayList();
    public List<String> generateParenthesis(int n) {
        dfs(n, new StringBuffer(), n, n);
        return ans;
    }
    
    private void dfs(int n, StringBuffer sb, int left, int right) {
        
        //剩下的右括号数量小于左括号数量那么一定不合法
        if(left > right)
            return ;
        
        if(left < 0 || right < 0)
            return ;
        
        if(left == 0 && right == 0) {
            ans.add(sb.toString());
            return ;
        }
        
        //先尝试左括号
        sb.append("(");
        dfs(n, sb, left - 1, right);
        sb.deleteCharAt(sb.length() - 1);
        
        //尝试右括号
        sb.append(")");
        dfs(n, sb, left, right - 1);
        sb.deleteCharAt(sb.length() - 1);
        
    }
    
}