// @Title: 括号生成 (Generate Parentheses)
// @Author: qisiii
// @Date: 2024-04-13 15:11:10
// @Runtime: 2 ms
// @Memory: 42.2 MB
// @comment: 回溯+剪枝
// @flag: WHITE
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        if(n<0){
            return result;
        }
        doAction("",n,n,result);
        return result;
    }
    /**
     *str 叶子节点
     *l左括号剩余的数量
     *r右括号剩余的数量
     *result 结果
     */
    public void doAction(String str,int l,int r,List<String> result){
        if(l==0&&r==0){
            result.add(str);
        }
        //剪枝，即剩余左括号数量大于剩余右括号数量时不是正规的括号,如")","(()"
        if(l>r){
            return;
        }
        if(l>0){
            doAction(str+"(",l-1,r,result);
        }
        if(r>0){
            doAction(str+")",l,r-1,result);
        }
    }

    
}