数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
有效括号组合需满足：左括号必须以正确的顺序闭合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
提示：
- 1 <= n <= 8
相关标签：字符串、动态规划、回溯
刚刚看完题目，我第一个想到的解法是用深度优先搜索，虽然题目提示用动态规划。
方法一：深度优先搜索
深度优先搜索属于图算法的一种，是一个针对图和树的遍历算法，英文缩写为DFS即Depth First Search。深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。
这题给了括号的个数n，满足题意的答案都是长度为2n的字符串，并且其中左括号个数和右括号个数是一样的。我们可以先确定第一个括号是说明，然后再这个基础上确定第二个括号，第三个…知道长度是2n。
合法的字符串有这几个特点
- 长度是括号个数n的两倍
- 左括号和右括号个数相等
- 如果左括号和右括号个数相等，但是长度还没到2*n的时候，下一个必定是左括号
- 如果左括号比右括号多，并且左括号个数小于n，下一个可以是左括号，也可以是右括号
- 如果左括号比右括号多，并且左括号个数等于n，下一个必定是右括号
基于这几点，接下来看看具体代码：
//深度优先搜索
public List<String> generateParenthesis(int n) {
if(n==0){
return new ArrayList<>();
}
//定义一个集合装符合要求的结果
List<String> list = new ArrayList<>();
getRes(list,n,0,0,new StringBuilder());
return list;
}
//left表示左括号个数，right表示右括号个数，n表示题目要求的括号个数
public void getRes(List<String> list,int n,int left,int right,StringBuilder s){
//获取字符串的长度
int len = s.length();
//如果长度是所给括号数的两倍，添加到集合中
if(s.length() == 2 * n){
list.add(s.toString());
}else {
//如果字符串中左括号数和右括号数一样
//必须添加左括号
if(left == right){
s.append('(');
getRes(list,n,left+1,right,s);
//删除调用函数前添加的‘（’，不然会对后面的代码造成影响
s.deleteCharAt(len);
}else if(left > right && left < n){
//这里可以添加左阔号或者右括号
char[] arr = new char[]{'(',')'};
for (char c : arr) {
s.append(c);
if (c == '(') {
getRes(list,n,left+1,right,s);
}else {
getRes(list,n,left,right+1,s);
}
s.deleteCharAt(len);
}
}else if(left > right && left == n){
//只能添加右括号
s.append(')');
getRes(list,n,left,right+1,s);
s.deleteCharAt(len);
}
}
}
本地idea调试结果（以3为例子）：
可以看出深度优先搜索都是一个个遍历完整之后，再返回去找下一个符合条件的答案。
方法二：广度优先搜索
广度优先搜索（也称宽度优先搜索，英文是Breadth-First Search，缩写BFS）是连通图的一种遍历算法这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。基本过程，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。一般用队列数据结构来辅助实现BFS算法。
以本题为例子，题目给了n个括号，然后需要找出所有符合条件的字符串，长度是2*n，广度优先搜索的思路是先找出所有第一个位置字符符合条件的组合，这里只有左括号满足条件，第二步是找出所有第一第二个位置都符合条件的组合，这里符合条件的有：((,()，依此类推，第三步符合条件的有：(((,((),()(…
在这个理论基础和前面字符串合法化的基础上，代码如下所示：
//广度优先搜索
public static List<String> generateParenthesis2(int n) {
if(n==0){
return new ArrayList<>();
}
//定义一个队列来存储可变字符串
Queue<StringBuilder> queue = new LinkedList<>();
//定义一个结果集
List<String> list = new ArrayList<>();
//添加初始值，刚开始只能添加左括号。
queue.offer(new StringBuilder("("));
//左右括号数组
char[] arr = {'(',')'};
while (!queue.isEmpty()){
//获取队列长度
int size = queue.size();
while (size!=0){
size--;
//获取队头元素
StringBuilder a = queue.poll();
if(a.length() == 2 * n){
list.add(a.toString());
}else {
int num = countLeftAndRight(a);
int left = num / 100;//左括号个数
int right = num % 100;//右括号个数
if(right == left){
//左括号和右括号数量相等，只能添加左括号
queue.offer(a.append('('));
}else if(left < n && left > right){
//左括号多于右括号并且左括号个数比括号数小
//左右括号都可以添加
for (char c : arr) {
a.append(c);
queue.offer(new StringBuilder(a));
a.deleteCharAt(a.length()-1);
}
}else if(left == n && right < left){
//左括号比右括号多，但是左括号已经是最大值了
//只能添加右括号
queue.offer(a.append(')'));
}
}
}
}
return list;
}
//这个方法用来计算字符串中左右括号的个数
public static int countLeftAndRight(StringBuilder s){
if (s.length()==0){
return 0;
}
int left = 0;//左括号的个数
int right = 0;//右括号的个数
for (int i = 0; i < s.length(); i++) {
if(s.charAt(i) == '('){
left++;
}else {
right++;
}
}
//百位以上表示左括号数量，其余表示右括号个数。
//题目说了n小于等于8，括号个数最大是8，所以10以上的倍数都可以
return left * 100 + right;
}
本地idea调试结果（以3为例子）：
对比一下对深度优先搜索和广度优先搜索有了更深的理解。
每天进步一点点，加油~
