问题描述
LeetCode 22. 括号生成 (opens in a new tab)，难度中等。
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1
输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2
输入：n = 1 输出：["()"]
提示：
1 <= n <= 8
题解
全排列 + 有效括号
解题思路：先根据 n 构建字符串，对字符串进行全排列，再对全排列的结果集合里面的每个元素进行有效括号检验，这个可以参考 20. 有效的括号 (opens in a new tab)。思路比较清晰，但时间复杂度比较高。
Solution.java
class Solution {
public List<String> generateParenthesis(int n) {
// 构建 n 个 () 的字符串
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; ++i) {
sb.insert(0, "(");
sb.append(")");
}
String str = sb.toString();
// 全排列
List<String> result = new ArrayList<>();
boolean[] used = new boolean[str.length()];
backtrack(result, new StringBuilder(), str, used);
return result;
}
public void backtrack(List<String> result, StringBuilder sb, String str, boolean[] used) {
// 如果 sb 的长度等于 str 的长度
if (sb.length() == str.length()) {
// 合法括号校验
if (isValid(sb.toString())) {
result.add(sb.toString());
}
return;
}
for (int i = 0; i < str.length(); ++i) {
if (used[i] || (i > 0 && str.charAt(i) == str.charAt(i - 1) && !used[i - 1])) {
continue;
}
used[i] = true;
sb.append(str.charAt(i));
backtrack(result, sb, str, used);
used[i] = false;
sb.deleteCharAt(sb.length() - 1);
}
}
public boolean isValid(String str) {
// 处理方法类似 LeetCode 20 题
Stack<Character> stack = new Stack<>();
for (int i = 0; i < str.length(); ++i) {
if (str.charAt(i) == ')') {
if (stack.isEmpty() || stack.pop() != '(')
return false;
} else {
stack.add(str.charAt(i));
}
}
return stack.isEmpty();
}
}