专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
一网友投递华为OD(外包)，直接反馈年龄不合适，后来得知，北京的华为OD只要27岁以下的，并且OD里学历人均985。学历限制也就认了，毕竟人多，择优录取。年龄还要限制到27岁，有的硕士毕业都27岁了，如果中国所有企业都这样搞，大家也不用读研了，因为毕业连一天班都不用上就已经超过年龄限制了。
网友评论：
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第22题：括号生成。
问题描述
来源：LeetCode第22题
难度：中等
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
示例1：
输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]
示例2：
输入：n = 1 输出：["()"]
1 <= n <= 8
问题分析
这题让生成 n 对有效的括号，任何有效的括号都会满足下面两个条件：
1，有效括号中左括号的数量等于右括号的数量。
2，有效括号中任何位置左括号的数量都大于等于右括号的数量。
第一条很容易理解，我们来看第二条，比如有效括号"(())()"，在任何一个位置右括号的数量都不大于左括号的数量，所以它是有效的。
如果像这样"())()"，第3个位置是右括号，那么它前面只有一个左括号，而它和它前面的右括号有2个，所以无论如何都不能构成有效的括号。我们就以 n 等于 2 为例来画个图看一下。
选择的过程实际上就是一棵二叉树， 左子树选择左括号，右子树选择右括号 ，选择的时候要剪掉一些不符合条件的分枝，到叶子节点的时候如果括号有效，就把它保存下来。
当左右括号的数量都选择完了就表示到叶子节点了，原理很清晰，我们来看下代码。
JAVA：
public List generateParenthesis (int n) { List
ans = new ArrayList<>(); dfs(ans, 0, 0, n, ""); return ans; } /** * @param ans 返回结果 * @param left 左括号的使用数量 * @param right 右括号的使用数量 * @param n * @param curStr 当前节点的字符串 */ private void dfs(List 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 + ")"); }C++：
public: vector
generateParenthesis(int n) { vector
ans; dfs(ans, 0, 0, n, ""); return ans; } /** * @param ans 返回结果 * @param left 左括号的使用数量 * @param right 右括号的使用数量 * @param n * @param curStr 当前节点的字符串 */ void dfs(vector
&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 + ")"); }
Python：
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笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
热门跟贴