22. 括号生成

image.png

利用的是回溯的思想，回溯其实就是二叉树不断的剪枝
首先来定义递归的出口
如果sb的长度等于2n，则说明递归要结束

image.png

如果左括号的长度小于n，则增加一个左括号

image.png
如果当前的左括号大于右括号，则添加右括号
image.png

class Solution {
    List<String> res=new ArrayList<>();
     StringBuilder sb=new StringBuilder();
    public List<String> generateParenthesis(int n) {
       
       back(0,0,n);
       return res;
    }
    public void back(int left,int right,int n){
       if(sb.length()==2*n){
           res.add(sb.toString());
           return;
       }  
       if(left<n){
           sb.append("(");
           back(left+1,right,n);
           sb.deleteCharAt(sb.length() - 1);
       }
       if (right < left) {
            sb.append(')');
            back(left, right+1, n);
            sb.deleteCharAt(sb.length() - 1);
        }




    }
}