LeetCode ——22、括号生成

题目链接:https://leetcode-cn.com/problems/generate-parentheses/

题目:数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

示例:

输入:n = 3 输出:[ "((()))", "(()())", "(())()", "()(())", "()()()" ]

网上这道题的解法很多:动态规划,回溯算法等等

由于目前我还没有搞明白动态规划,所以就先说另一种方法……

我在这里要分享的是 :递归+剪枝

方法1:递归

递归搜索出所有的可能结果,之后再判断括号是否合法,最后找出所有可能的结果。

这种方法的时间复杂度是O(2n)2的n次方,虽然能解决问题,但是复杂度还是太高了,所以还有优化的空间。

方法2:递归+剪枝

在递归的过程中,我们可以加入一些限制条件,在某些情况下不再递归下去。 比如:

  1. 第一个就是右括号;
  2. 拼接的括号里右括号多于左括号;
  3. 左右括号数量多于给定的数量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);
        }
    }
}
end

评论