1. package treeAndRecursion.code22;
    3. import java.util.ArrayList;
    4. import java.util.List;
    6. public class Solution {
    7.     public List<String> result = new ArrayList<>();
    9.     /**
    10.      * 整体思想就是深度优先遍历，产生出所有可能性组合的二叉树。然后剪枝剔除掉不合法的。
    11.      * @param n
    12.      * @return
    13.      */
    14.     public List<String> generateParenthesis(int n) {
    15.         bfs("",n,n);
    16.         return result;
    17.     }
    19.     /**
    20.      * 深度优先遍历
    21.      * @param chosen 当前已经选择了的字符串
    22.      * @param left 当前左括号可用个数
    23.      * @param right 当前有括号可用个数
    24.      */
    25.     public void bfs(String chosen,int left,int right){
    26.         //递归结束条件。当左右括号都没有能用的了，就存储结果，并结束递归。
    27.         if(left == 0 && right == 0){
    28.             result.add(chosen);
    29.             return;
    30.         }
    31.         //剪枝。当只有可用的右括号  >  可用的左括号，才是一个合法的组合。
    32.         // 因为如果左括号数比右括号多了，说明右边已经阔不回去了，就是不合法的了
    33.         if(left > right){
    34.             return;
    35.         }
    36.         //如果有可选的左括号。产生一个选择了左括号的左子树。
    37.         if(left > 0){
    38.             bfs(chosen + "(",left-1,right);
    39.         }
    40.         //如果有可选的左括号。产生一个选择了右括号的右子树。
    41.         if(right > 0){
    42.             bfs(chosen + ")", left, right-1);
    43.         }
    44.     }
    45. }