穷举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--;}}