题目描述
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例
输入：n = 3
输出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
解题思路
- 利用二叉树的遍历。参考：https://leetcode-cn.com/problems/generate-parentheses/solution/hui-su-suan-fa-by-liweiwei1419/
代码
public List<String> generateParenthesis(int n) {
if (n <= 0) {
return null;
}
List<String> result = new ArrayList<>();
dfs("", 0, 0, n, result);
return result;
}
/**
* @param prefix 当前的字符串
* @param left 左括号用了几个
* @param right 右括号用了几个
* @param size 生成括号的对数
* @param result 结果
*/
void dfs(String prefix, int left, int right, int size, List<String> result) {
if ( left == right && left == size) {
// 左右括号使用的个数相同，并且都用完了，则是符合条件的括号组合。
result.add(prefix);
return;
}
if (left < right) {
// 如果当前已使用左括号的数量小于右括号的数量，则无法形成有效的括号。直接return。
return;
}
if (left < size) {
dfs(prefix + "(", left + 1, right, size, result);
}
if (right < size) {
dfs(prefix + ")", left, right + 1, size, result);
}
}
