算法-字符串-22.括号生成

一、题目

二、思路解析

        1.思路：

                生成所有可能并且有效的括号组合——回溯方法

        2.常用方法：

                a.数组，因为需要增删元素，所以选择LinkedList

LinkedList<String> res=new LinkedList<>();

                b.StringBuilder创建，因为要拼接字符

StringBuilder sb=new StringBuilder();

                 c.删除sb中的某一个字符，因为要进行回溯

sb.deleteCharAt(s.length()-1);

                d.stringBuilder对象转string对象

String str=sb.toString();

        3.核心逻辑：

                a.回溯模板：

void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果}
}

         b.终止条件：当sb中的长度等于n*2时

if(sb.length()==n*2){res.add(sb.toString());return ;
}

        c.回溯过程：

                 首先，必然是先放'('，才会有效，同时'('的数量不能超过n

if(open<n){sb.append('(');back(res,sb,n,open+1,close);//进行回溯sb.deleteCharAt(sb.length()-1);
}

                当'('的数量大于')'的时候，就可以放入')'是有效的

if(close<open){sb.append(')');back(res,sb,n,open,close+1);sb.deleteCharAt(sb.length()-1);
}

三、代码实现

class Solution {public List<String> generateParenthesis(int n) {List<String> res=new LinkedList<String>();StringBuilder sb=new StringBuilder();back(res,sb,n,0,0);return res;}void back(List<String> res,StringBuilder sb,int n,int open,int close){if(sb.length()==n*2){res.add(sb.toString());return ;}if(open<n){sb.append('(');back(res,sb,n,open+1,close);sb.deleteCharAt(sb.length()-1);}if(close<open){sb.append(')');back(res,sb,n,open,close+1);sb.deleteCharAt(sb.length()-1);}}
}