问题描述
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
示例:
输入:n = 3
输出:[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
解答
- 第一个肯定是左括号
- 如果剩余有左括号,放左括号是没有任何问题的
- 在已经放的左括号多余右括号的情况下,也就是剩余的右括号比左括号多,才可以放右括号
ArrayList<String> list = new ArrayList<>();
public List<String> solution(int n) {
dfs(n, n, "");
return list;
}
public void dfs(int left, int right, String curStr) {
// 左右括号都放完,方法返回
// 最后一个肯定是右括号,所以一定是递归2返回
// 然后一直回溯到递归1返回,然后继续递归2
if (left == 0 && right == 0) {
list.add(curStr);
return;
}
// 递归1:有左括号就放左括号
if (left > 0) {
dfs(left -1, right, curStr + "(");
}
// 递归2:剩余的右括号更多时,可以放右括号
if (right > left) {
dfs(left, right - 1, curStr + ")");
}
}
网友评论