题目链接:https://leetcode-cn.com/problems/generate-parentheses/
题目:数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
示例:
输入:n = 3 输出:[ "((()))", "(()())", "(())()", "()(())", "()()()" ]
网上这道题的解法很多:动态规划,回溯算法等等
由于目前我还没有搞明白动态规划,所以就先说另一种方法……
我在这里要分享的是 :递归+剪枝
方法1:递归
递归搜索出所有的可能结果,之后再判断括号是否合法,最后找出所有可能的结果。
这种方法的时间复杂度是O(2n)2的n次方,虽然能解决问题,但是复杂度还是太高了,所以还有优化的空间。
方法2:递归+剪枝
在递归的过程中,我们可以加入一些限制条件,在某些情况下不再递归下去。 比如:
- 第一个就是右括号;
- 拼接的括号里右括号多于左括号;
- 左右括号数量多于给定的数量n。
接下来看代码:
class Solution {
public List<String> generateParenthesis(int n) {
List<String> list = new ArrayList<>();
generate("", list, n, n);
return list;
}
// 辅助函数 left,right:左右括号可使用的数量
public void generate(String str, List<String> result, int left, int right) {
// 如果左右括号都用完了就结束递归
if (left==0&&right==0) {
result.add(str);
return;
}
// 只要左括号没用完,都可以加
if (left>0) {
generate(str+"(", result, left-1, right);
}
// 只要右括号可用数量比左括号多就可以加
if (right>left) {
generate(str+")", result, left, right-1);
}
}
}
评论