22. 括号生成
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
示例 1:
输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]
示例 2:
输入:n = 1
输出:["()"]
解析
要注意剪枝操作。假设N=3,我们先去填充左括号,然后再去填充右括号,一直满足左3右3。这时候第一轮递归结束,然后我们回退到左2的栈中,继续执行right的递归,这里注意right>left 既不用看了,直接跳过。
public class Solution1112 {
// 做加法
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
// 特判
if (n == 0) {
return res;
}
dfs("", 0, 0, n, res);
return res;
}
/**
* @param curStr 当前递归得到的结果
* @param left 左括号已经用了几个
* @param right 右括号已经用了几个
* @param n 左括号、右括号一共得用几个
* @param res 结果集
*/
private void dfs(String curStr, int left, int right, int n, List<String> res) {
if (left == n && right == n) {
res.add(curStr);
return;
}
// 剪枝
if (left < right) {
return;
}
if (left < n) {
dfs(curStr + "(", left + 1, right, n, res);
}
if (right < n) {
dfs(curStr + ")", left, right + 1, n, res);
}
}
}
注意:本文归作者所有,未经作者允许,不得转载