关键词：
数字 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为例子）：
对比一下对深度优先搜索和广度优先搜索有了更深的理解。
每天进步一点点，加油~
力扣刷题：合并区间（java实现）(代码片段)
题目描述：以数组intervals表示若干个区间的集合，其中单个区间为intervals[i]=[starti,endi]。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。示例1：输入：in... 查看详情
力扣刷题：寻找峰值（java实现）(代码片段)
题目：峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。你可以假设nums[-1]=nums[n]=... 查看详情
力扣刷题：岛屿数量（java实现）(代码片段)
给你一个由'1'（陆地）和'0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以... 查看详情
力扣刷题：全排列（java实现）(代码片段)
题目：给定一个不含重复数字的数组nums，返回其所有可能的全排列。你可以按任意顺序返回答案。示例1：输入：nums=[1,2,3]输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例2：输入：nums=[0,1]输出&#x... 查看详情
力扣刷题：字母异位词分组（java实现）(代码片段)
题目：给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。字母异位词是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母都恰好只用一次。示例1:输入:strs=["eat... 查看详情
力扣刷题：单词搜索（java实现）(代码片段)
题目：给定一个mxn二维字符网格board和一个字符串单词word。如果word存在于网格中，返回true；否则，返回false。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相... 查看详情
力扣刷题：快乐数（java实现）(代码片段)
题目描述：编写一个算法来判断一个数n是不是快乐数。「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为1，也可能是无限循环但始终变... 查看详情
力扣刷题：最长回文子串（java实现）(代码片段)
题目：给你一个字符串s，找到s中最长的回文子串。示例1：输入：s="babad"输出："bab"解释："aba"同样是符合题意的答案。【个人建议最好取第一个】示例2：输入：s="cbbd"... 查看详情
力扣刷题：前k个高频元素（java实现）(代码片段)
题目：给你一个整数数组nums和一个整数k，请你返回其中出现频率前k高的元素。你可以按任意顺序返回答案。示例1:输入:nums=[1,1,1,2,2,3],k=2输出:[1,2]示例2:输入:nums=[1],k=1输出:[1]提示：1<=nums.length<=... 查看详情
力扣刷题：电话号码的字母组合（java实现）(代码片段)
题目：给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下（与电话按键相同）。注意1不对应任何字母。示例1：输入：digits="23"... 查看详情
力扣刷题：矩阵置零（java实现）(代码片段)
题目：给定一个mxn的矩阵，如果一个元素为0，则将其所在行和列的所有元素都设为0。请使用原地算法。进阶：一个直观的解决方案是使用O(mn)的额外空间，但这并不是一个好的解决方案。一个简单的改进方案... 查看详情
力扣刷题：三数之和（java实现）(代码片段)
题目：给你一个包含n个整数的数组nums，判断nums中是否存在三个元素a，b，c，使得a+b+c=0？请你找出所有和为0且不重复的三元组。标签：数组，双指针，排序注意：答案中不可以包... 查看详情
力扣刷题：无重复字符的最长子串（java实现）(代码片段)
题目：给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。示例1:输入:s="abcabcbb"输出:3解释:因为无重复字符的最长子串是“abc”，所以其长度为3。示例2:输入:s="bbbbb"输出:1解释:因为... 查看详情
力扣刷题：从前序与中序遍历序列构造二叉树（java实现）(代码片段)
题目：给定一棵树的前序遍历preorder与中序遍历inorder。请构造二叉树并返回其根节点。示例1:Input:preorder=[3,9,20,15,7],inorder=[9,3,15,20,7]Output:[3,9,20,null,null,15,7]示例2:Input:preorder=[-1],inorder=[-1]Output:[- 查看详情
力扣刷题：填充每个节点的下一个右侧节点指针（java实现）(代码片段)
题目：给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：structNodeintval;Node*left;Node*right;Node*next;填充它的每个next指针，让这个指针指向其下一个右侧节点。如果... 查看详情
力扣刷题详解(含代码动态展示)(代码片段)
(文章目录)一、448.找到所有数组中消失的数字1.完整过程动态展示2.代码实现int*findDisappearedNumbers(int*nums,intnumsSize,int*returnSize)int*ptr=(int*)malloc(sizeof(int)*numsSize);intindex=0;intnoindex=0;while(index<numsSize)if(num 查看详情
力扣刷题每日打卡(代码片段)
力扣刷题：重新排列数组：/***Note:Thereturnedarraymustbemalloced,assumecallercallsfree().*/int*shuffle(int*nums,intnumsSize,intn,int*returnSize)if(numsSize==1)*returnSize=1;returnnums;in 查看详情
力扣刷题每日打卡(代码片段)
力扣刷题：重新排列数组：/***Note:Thereturnedarraymustbemalloced,assumecallercallsfree().*/int*shuffle(int*nums,intnumsSize,intn,int*returnSize)if(numsSize==1)*returnSize=1;returnnums;in 查看详情