穷举vs暴搜vs深搜vs回溯vs剪枝系列一＞括号生成

题目： 

 

---

解析：  

该题：

---

 1.决策树： 

 

---

2.代码设计： 

2.1.全局变量： 

 

---

2.2. 

 

---

代码： 

private List<String> ret;
    private int left,n,right;
    private StringBuffer path;
    public List<String> generateParenthesis(int _n) {
        n = _n;

        ret = new ArrayList<>();
        path = new StringBuffer();
        dfs();
        return ret;
    } 

    private void dfs(){
        //递归出口
        if(right == n) {
            ret.add(path.toString());
            return;
        }

        /** 
        剪枝写法:
         */ 
        
        //添加左括号
        if(left < n){
            path.append("("); left++;
            dfs();
            //回溯：恢复现场
            path.deleteCharAt(path.length()-1); left--;
        } 

        //添加右括号：右括号永远满足 <= 左括号
        if(right < left) {
            path.append(")"); right++; 
            dfs();
           //回溯：恢复现场
           path.deleteCharAt(path.length()-1); right--;
        }
    }