题目
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
提示：
1 <= n <= 8
解法1（正确）
思路：利用递归的思想，列举出括号组合的所有可能，再进行判断是否是有效的括号组合。
代码：
public class Solution {
public List<String> generateParenthesis(int n) {
List<String> list = new ArrayList<>();
char[] ch = new char[2 * n];
get(ch, 0, list);
return list;
}
private void get(char[] ch, int current, List<String> list) {
if (current == ch.length) {
if (valid(ch)) {
list.add(new String(ch));
}
} else {
ch[current] = '(';
get(ch, current + 1, list);
ch[current] = ')';
get(ch, current + 1, list);
}
}
private boolean valid(char[] ch) {
int balance = 0;
for (char c : ch) {
if (c == '(') {
balance++;
} else {
balance--;
}
if (balance < 0) {
return false;
}
}
if (balance > 0) {
return false;
} else {
return true;
}
}
}
结果：
8 / 8 个通过测试用例
状态：通过
执行用时: 2 ms
内存消耗: 38.8 MB
官方解答：