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

题目

解题思路

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(")"));
        }
    }
}