题目出处
题目描述
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
提示：
1 <= n <= 8
个人解法
思路：
todo
代码示例：（Java）
todo
复杂度分析
todo
官方解法
方法1：暴力法
思路：
代码示例：（Java）
public List<String> generateParenthesis(int n) {
List<String> combinations = new ArrayList<String>();
generateAll(new char[2 * n], 0, combinations);
return combinations;
}
public void generateAll(char[] current, int pos, List<String> result) {
if (pos == current.length) {
if (valid(current)) {
result.add(new String(current));
}
} else {
current[pos] = '(';
generateAll(current, pos + 1, result);
current[pos] = ')';
generateAll(current, pos + 1, result);
}
}
public boolean valid(char[] current) {
int balance = 0;
for (char c : current) {
if (c == '(') {
++balance;
} else {
--balance;
}
if (balance < 0) {
return false;
}
}
return balance == 0;
}
复杂度分析
方法2:回溯法
思路：
方法一还有改进的余地：我们可以只在序列仍然保持有效时才添加 ‘(’ 或 ‘)’，而不是像 方法一 那样每次添加。我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点，
如果左括号数量不大于 n，我们可以放一个左括号。如果右括号数量小于左括号的数量，我们可以放一个右括号。
代码示例：（Java）
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList<String>();
backtrack(ans, new StringBuilder(), 0, 0, n);
return ans;
}
public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
if (cur.length() == max * 2) {
ans.add(cur.toString());
return;
}
if (open < max) {
cur.append('(');
backtrack(ans, cur, open + 1, close, max);
cur.deleteCharAt(cur.length() - 1);
}
if (close < open) {
cur.append(')');
backtrack(ans, cur, open, close + 1, max);
cur.deleteCharAt(cur.length() - 1);
}
}
复杂度分析
方法3:按括号序列的长度递归
思路：
任何一个括号序列都一定是由 ‘(’ 开头，并且第一个 ‘(’ 一定有一个唯一与之对应的 ‘)’。这样一来，每一个括号序列可以用 (a)b 来表示，其中 a 与 b 分别是一个合法的括号序列（可以为空）。
那么，要生成所有长度为 2n 的括号序列，我们定义一个函数 generate(n) 来返回所有可能的括号序列。那么在函数 generate(n) 的过程中：
我们需要枚举与第一个 ‘(’ 对应的 ‘)’ 的位置 2i+1；
递归调用 generate(i) 即可计算 a 的所有可能性；
递归调用 generate(n−i−1) 即可计算 b 的所有可能性；
遍历 a 与 b 的所有可能性并拼接，即可得到所有长度为 2n 的括号序列。
为了节省计算时间，我们在每次 generate(i) 函数返回之前，把返回值存储起来，下次再调用 generate(i) 时可以直接返回，不需要再递归计算。
代码示例：（Java）
ArrayList[] cache = new ArrayList[100];
public List<String> generate(int n) {
if (cache[n] != null) {
return cache[n];
}
ArrayList<String> ans = new ArrayList<String>();
if (n == 0) {
ans.add("");
} else {
for (int c = 0; c < n; ++c) {
for (String left : generate(c)) {
for (String right : generate(n - 1 - c)) {
ans.add("(" + left + ")" + right);
}
}
}
}
cache[n] = ans;
return ans;
}
public List<String> generateParenthesis(int n) {
return generate(n);
}
复杂度分析
