22. 括号生成 --力扣 --JAVA

题目

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

解题思路

1. n个括号，即拥有n个左括号和n个右括号，且在拼接字符串的过程中左括号的数量应该永远大于等于右括号的数量；
2. 当左括号的数量大于右括号且小于n的时候，允许添加左括号，当左括号的数量等于右括号时只允许添加左括号；

代码展示

class Solution {
    List<String> ans = new ArrayList<>();
    int size;
    public List<String> generateParenthesis(int n) {
        size = n;
        dfs(0,0,new StringBuilder());
        return ans;
    }
    private void dfs( int left, int right, StringBuilder sb){
        if(right == size){
            ans.add(sb.toString());
            return;
        }
        if(left == right){
            dfs(left + 1,right,new StringBuilder(sb).append("("));
        } else if(left > right){
            if(left < size){
                dfs(left + 1,right,new StringBuilder(sb).append("("));

            }
            dfs(left,right + 1,new StringBuilder(sb).append(")"));
        }
    }
}