精品推荐：
《征服数据结构》专栏：50多种数据结构彻底征服
《经典图论算法》专栏：50多种经典图论算法全部掌握
一网友投递华为OD(外包)，直接反馈年龄不合适，后来得知，北京的华为OD只要27岁以下的，并且OD里学历人均985。学历限制也就认了，毕竟人多，择优录取。年龄还要限制到27岁，有的硕士毕业都27岁了，如果中国所有企业都这样搞，大家也不用读研了，因为毕业连一天班都不用上就已经超过年龄限制了。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第22题：括号生成。
问题描述
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
输入：n = 1
输出：["()"]
1 <= n <= 8
问题分析
1，有效括号中左括号的数量等于右括号的数量。
2，有效括号中任何位置左括号的数量都大于等于右括号的数量。
第一条很容易理解，我们来看第二条，比如有效括号"(())()"，在任何一个位置右括号的数量都不大于左括号的数量，所以它是有效的。
如果像这样"())()"，第3个位置是右括号，那么它前面只有一个左括号，而它和它前面的右括号有2个，所以无论如何都不能构成有效的括号。我们就以 n 等于 2 为例来画个图看一下。
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList<>();
dfs(ans, 0, 0, n, "");
return ans;
}
/**
* @param ans 返回结果
* @param left 左括号的使用数量
* @param right 右括号的使用数量
* @param n
* @param curStr 当前节点的字符串
*/
private void dfs(List<String> ans, int left, int right, int n, String curStr) {
if (left == n && right == n) {
// 左右括号都使用完了，说明找到了有效的括号
ans.add(curStr);
return;
}
// 选择左括号，左右括号的数量都不能大于n
if (left < n)
dfs(ans, left + 1, right, n, curStr + "(");
// 选择右括号，右括号数量不能大于左括号的数量。
if (right < left)// 注意这里不能写等号，
dfs(ans, left, right + 1, n, curStr + ")");
}
public:
vector<string> generateParenthesis(int n) {
vector<string> ans;
dfs(ans, 0, 0, n, "");
return ans;
}
/**
* @param ans 返回结果
* @param left 左括号的使用数量
* @param right 右括号的使用数量
* @param n
* @param curStr 当前节点的字符串
*/
void dfs(vector<string> &ans, int left, int right, int n, string curStr) {
if (left == n && right == n) {
// 左右括号都使用完了，说明找到了有效的括号
ans.push_back(curStr);
return;
}
// 选择左括号，左右括号的数量都不能大于n
if (left < n)
dfs(ans, left + 1, right, n, curStr + "(");
// 选择右括号，右括号数量不能大于左括号的数量。
if (right < left)// 注意这里不能写等号，
dfs(ans, left, right + 1, n, curStr + ")");
}
def generateParenthesis(self, n: int) -> List[str]:
def dfs(curStr, left, right):
if left == n and right == n:
# 左右括号都使用完了，说明找到了有效的括号
ans.append(curStr)
return
# 选择左括号，左右括号的数量都不能大于n
if left < n:
dfs(curStr + "(", left + 1, right)
# 选择右括号，右括号数量不能大于左括号的数量。
if right < left: # 注意这里不能写等号，
dfs(curStr + ")", left, right + 1)
ans = []
dfs("", 0, 0)
return ans
数组，稀疏表(Sparse Table)，单向链表，双向链表，块状链表，跳表，队列和循环队列，双端队列，单调队列，栈，单调栈，双端栈，散列表，堆，字典树(Trie树)，ArrayMap，SparseArray，二叉树，二叉搜索树(BST)，笛卡尔树，AVL树，树堆(Treap)，FHQ-Treap，哈夫曼树，滚动数组，差分数组，LRU缓存，LFU缓存
……
图的介绍，图的表示方式，邻接矩阵转换，广度优先搜索(BFS)，深度优先搜索(DFS)，A*搜索算法，迭代深化深度优先搜索(IDDFS)，IDA*算法，双向广度优先搜索，迪杰斯特拉算法(Dijkstra)，贝尔曼-福特算法(Bellman-Ford)，SPFA算法，弗洛伊德算法(Floyd)，卡恩(Kahn)算法，基于DFS的拓扑排序，约翰逊算法(Johnson)
……
