题解 | #括号生成#

//思路：有效的括号组合，“（”总是在“）”之前出现，如果“）”在“（”之前出现了，那么是无效的组合，所以本题是找出所有有效的解，采用DFS和回溯算法。

10. //创建一个List用于放最后的结果
11. ArrayList<string> res = new ArrayList<string>();</string></string>
12. public ArrayList<string> generateParenthesis (int n) {</string>
13. //排除没有括号情况
14. if(n < 1) {
15. return res;
16. }
17. //有括号，DFS和回溯算法
18. String str ="";
19. dfs(str,res,n,n);
20. return res;
21. }
22. public void dfs(String str,List<string> res,int left,int right){</string>
23. //左右括号都分配完了，则将组合str添加到结果res
24. if(left==0 && right ==0){
25. res.add(str);
26. }
27. -
28. //只有当“（”比“）”数量多时，才可以添加“）”
29. if(left>0){
30. str = str + "(";
31. dfs(str,res,left-1,right);
32. //删除最后一项，也就是进行回溯
33. str =str.substring(0,str.length()-1);
34. }
35. if(right > left){
36. str = str + ")";
37. dfs(str,res,left,right-1);
38. //同理，进行回溯
39. str = str.substring(0,str.length()-1);
40. }
41. }
42. }