题目
数字 n
代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且
有效的 括号组合。
示例 1：
1
2
| 输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
|
示例 2：
提示：
题解
这一题依然使用回溯的方法解决：
回溯的结束条件是，如果cur字符串的长度为2 * n是，把cur加入到ans中，返回即可；
然后先回溯左括号，当左括号的数目小于n时，把左括号加入到cur中，然后继续backtrack，条件里左括号的数目+1，回溯完cur删除最后一个左括号恢复；
然后回溯右括号，当右括号数目小于左括号数目的时候，把右括号加入到cur中，继续回溯，条件里右括号的数目+1，回溯完记得删除最后一个恢复。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
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);
}
}
}
|